10101...101

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

1 user

TOPICS

No tags match your search

M

No tags match your search

M

10101...101

G H J

Reveal topic tags

difference of squares

special factorizations

college contests

L

G H BBookmark kLocked kLocked NReply

Source: Putnam

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CatalystOfNostalgia

1479 posts

CatalystOfNostalgia

#1 h Nov 11, 2007, 12:09 AM • 2 Y

Y by Adventure10, Mango247

How many base ten integers of the form 1010101...101 are prime?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#2 h Nov 11, 2007, 3:34 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23508 posts

pco

#3 h Nov 11, 2007, 8:58 AM • 2 Y

Y by Adventure10, Mango247

t0rajir0u wrote:

Unfortunately, t0rajir0u

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

341 posts

#4 h Nov 11, 2007, 9:45 AM • 2 Y

Y by Adventure10, Mango247

if $n$ is even. the number is divisible by $101$
if $n$ is odd. then $\frac {10^{n + 1} - 1}{10 - 1}$ divides $\frac {100^{n + 1} - 1}{100 - 1}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23508 posts

pco

#5 h Nov 11, 2007, 9:53 AM • 2 Y

Y by Adventure10, Mango247

Fraenkel wrote:

if $n$ is even. the number is divisible by $101$
if $n$ is odd. then $\frac {10^{n + 1} - 1}{10 - 1}$ divides $\frac {100^{n + 1} - 1}{100 - 1}$

Could you be more clear ?

Are you speaking of $S_n=\frac{10^{2n}-1}{99}$ ?

If so , you said :
If $n$ is even, $S_n$ is not prime.
If $n$ is odd, $S_{n+1}$ is not prime.

So you said twice that $S_{2p}$ is not prime.

Do I miss something ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

341 posts

#6 h Nov 11, 2007, 10:17 AM • 2 Y

Y by Adventure10, Mango247

all numbers in the form $101010...101$ are trivially divisible by $101$ if there are an even number of $1$ 's
$101$
$1010101$ and so on...

if there are an odd number of $1$ 's. I am claiming that:
$10101...0101$ with $k$ one's is divisible by $111111....111$ which is a number with $k$ ones.
$\frac{10101}{111}=91$
$\frac{101010101}{11111}=9091$
$\frac{1010101010101}{1111111}=909091$

As an exercise you should show this is true for all $n$ .

Hence by conclusion the only number prime is $101$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1039 posts

#7 h Nov 11, 2007, 10:50 AM • 2 Y

Y by Adventure10, Mango247

Let: $N=1+10^{2}+.....+10^{2n} = \frac{10^{2n+2}-1}{99}= \frac{(10^{n+1}-1)(10^{n+1}+1)}{99}$

Hence $11N = (10^{n+1}+1)(1+10+10^{2} + ...... +10^{n})$

$11$ is prime so it divides one of the two expression on the RHS.

For $n=1$ : the second expression is $1+10 =11$ and $N=101$ which is prime.

For all $n \geq 2$ the two expressions are greater than $1$ and hence $N$ can be written as the product of two integers greater than $1$ . Hence $N$ is composite.

Therefore $N=101$ is the only prime number in the series.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

12167 posts

#8 h Nov 11, 2007, 7:51 PM • 2 Y

Y by Adventure10, Mango247

pco wrote:

t0rajir0u wrote:

Unfortunately, t0rajir0u

My apologies. Let me modify my argument: when $n$ is odd, $\frac{10^n + 1}{10 + 1} | \frac{100^n - 1}{100 - 1}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

383 posts

#9 h Nov 12, 2007, 9:47 AM • 2 Y

Y by Adventure10, Mango247

This problem was also asked in the 4th round of the 2007 German math olympiad.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1039 posts

#10 h Nov 12, 2007, 9:50 AM • 2 Y

Y by Adventure10, Mango247

bertram wrote:

This problem was also asked in the 4th round of the 2007 German math olympiad.

Apparantly this is also a question from the Senior Division of the New Zealand September Problem Set for selection to the NZIMO Camp.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

148 posts

bwu

#11 h Nov 3, 2008, 1:04 AM • 2 Y

Y by Adventure10 and 1 other user

thanks. this was an excellent problem and solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

553 posts

#12 h Jul 2, 2009, 3:42 AM • 1 Y

Y by Adventure10

Letting $a_n = \sum_{i=0}^{n} 100^n$ , we have $a_{2n}$ with $2n+1$ 1's. and $2n$ 0's. Then $a_{2n} + 100^n = a_n^2$ , so it is just a difference of squares: $a_{2n} = (a_n+10^n)(a_n-10^n)$ . This suffices to prove Fraenkel's claim.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1502 posts

SCP

#13 h Dec 10, 2012, 6:11 PM • 2 Y

Y by Adventure10, Mango247

So it can be posted as Putnam 1989/ A1 in contest togeter with all other ones. (?)

Remark that if $n>2$ then $99< 10^n-1,10^n+1$ and hence it has at least two prime factors, done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#14 h Apr 5, 2022, 10:11 AM

Y by

Claim: There's only $1$ which is $101.$

Proof. Let $n$ be the number of 1s with $n\geq 2.$ Notice that,
$99(1010101\dots 101)=99\dots 999=10^{2n}-1=(10^n+1)(10^n-1).$

So our required primes must divide $10^n\pm 1$ , implying that
$\frac{99}{10^n\pm 1}=\frac{10^n\mp 1}{10101\dots 101}$ is an integer.
This is true iff $n=2$ , thus the prime is $\boxed{101}$ .

This post has been edited 1 time. Last edited by ZETA_in_olympiad, Apr 5, 2022, 10:11 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

420 posts

Sagnik123Biswas

#15 h Apr 4, 2025, 4:41 PM

Y by

If $n$ is odd, then $a_n = \frac{10^n + 1}{11} \times \frac{10^n-1}{9}$ . If $n = 1$ , then $a_n = 1$ . Otherwise, $\frac{10^n + 1}{11}$ and $\frac{10^n-1}{9}$ are both integers larger than $1$ . None of these are prime

If $n$ is even, then $a_n \equiv \sum_{i=0}^{n-1} (-1)^{i} \equiv 0 \pmod{101}$ . So it follows that only $a_2$ is prime since $a_n > 101$ for $n > 2$ .

So only $101$ is prime.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a