a) Is the number $ 1111\cdots11$ (with $ 2010$ ones) a prime number? b) Prove that every prime factor of $ 1111\cdots11$ (with $ 2011$ ones) is of the form $ 4022j+1$ where $ j$ is a natural number.
Problem
Source: Albanian BMO TST 2010 Question 1
Tags: modular arithmetic, number theory unsolved, number theory
20.03.2010 16:02
a)$ 11...1$ (with $ 2010$ ones)$ = \frac {10^{2010} - 1}{9} = \frac {10^{1005} - 1}{9}.(10^{1005} + 1)$ isn't a prime number. b)$ 11...1$ (with $ 2011$ ones)$ = \frac {10^{2011} - 1}{9}$. Assume $ p|\frac {10^{2011} - 1}{9}$, then $ p|10^{2011} - 1$. $ p|10^{p - 1} - 1$ then $ p|10^{(p - 1,2011)} - 1$. But $ (p,9) = 1$ so $ p - 1\vdots 2011$, $ p$ odd hence $ p - 1\vdots 4022$. $ p = 4022k + 1$.
20.03.2010 23:39
ridgers wrote: a) Is the number $ 1111\cdots11$ (with $ 2010$ ones) a prime number? b) Prove that every prime factor of $ 1111\cdots11$ (with $ 2011$ ones) is of the form $ 4022j + 1$ where $ j$ is a natural number. a) Solution given above by Thjch Ph4 Trjnh was my first solution too. I will post my second solution to this problem. Lemma: Let $ A=f(x)=a_{n-1}x^{n-1} +a_{n-2}x^{n-2} +...+a_1 x +a_0$, if $ a_0 -a_1 +a_2 -a_3 +a_4- ...$ is divisible by $ 11$ then $ A$ is divisible by $ 11$ too. Proof: Since $ 10\equiv -1 \pmod {11}$ then $ f(10) \equiv f(-1) \pmod {11} \implies A\equiv a_0 -a_1 +a_2 -a_3 +a_4 -... \pmod {11}$ $ \implies A$ is divisible by $ 11 \iff a_0 -a_1 +a_2 -a_3 +a_4 - ...$ is divisible by $ 11$. Now, observe that in our case $ a_0 =a_1 =...=a_{2009}=1$, therefore $ a_0 -a_1 +a_2 -a_3 +a_4 -...-a_{2009}=0$, therefore $ 111...1$ is divisible by $ 11$. In more general, every $ 111...1$ (with $ 2p$ ones) is divisible by $ 11$. b)
21.03.2010 14:14
1 is simply done,11 divides it as the number of 1`s is even
07.06.2010 20:18
also 3 divides the number since it divides the sum of the digits
08.06.2010 05:08
Question 1 is simple to solve as $3 \mid 2010$ but $9\nmid 2010$. Question 2, Note that 2011 is prime. $1111.....1111(with 2011 ones) =\frac{10^{2011}-1}{9}$ Using Fermet's theorem $10^{2010}\equiv 1$ (mod 2011) $10^{2011}\equiv 10$ (mod 2011) Also $10-1=9$ gives $10^{2011}\equiv 1\equiv-9\equiv 10$ (mod 9) Thus, $\frac{10^{2011}}{9}\equiv\frac{10}{9}$ (mod 2011) becos $(9,2011)=1$ $\Rightarrow$ $\frac{10^{2011}}{9}\equiv\frac{1}{9}+1$ (mod 2011) $\Rightarrow$ $\frac{10^{2011}-1}{9}\equiv 1$ (mod 2011) $\frac{10^{2011}-1}{9}\equiv 1$ (mod 2) Since $(2,2011)=1$ Thus, $4022j+1 =11111...11111$(with 2011 ones)
22.12.2010 16:50
rationalist wrote: Question 1 is simple to solve as $3 \mid 2010$ but $9\nmid 2010$. Question 2, Note that 2011 is prime. $1111.....1111(with 2011 ones) =\frac{10^{2011}-1}{9}$ Using Fermet's theorem $10^{2010}\equiv 1$ (mod 2011) $10^{2011}\equiv 10$ (mod 2011) Also $10-1=9$ gives $10^{2011}\equiv 1\equiv-9\equiv 10$ (mod 9) Thus, $\frac{10^{2011}}{9}\equiv\frac{10}{9}$ (mod 2011) becos $(9,2011)=1$ $\Rightarrow$ $\frac{10^{2011}}{9}\equiv\frac{1}{9}+1$ (mod 2011) $\Rightarrow$ $\frac{10^{2011}-1}{9}\equiv 1$ (mod 2011) $\frac{10^{2011}-1}{9}\equiv 1$ (mod 2) Since $(2,2011)=1$ Thus, $4022j+1 =11111...11111$(with 2011 ones) There are some mistakes in it and you only prove $\frac{10^{2011}-1}{9}\equiv 1 \pmod {4022}$
22.12.2010 16:54
Thjch Ph4 Trjnh wrote: a)$ 11...1$ (with $ 2010$ ones)$ = \frac {10^{2010} - 1}{9} = \frac {10^{1005} - 1}{9}.(10^{1005} + 1)$ isn't a prime number. b)$ 11...1$ (with $ 2011$ ones)$ = \frac {10^{2011} - 1}{9}$. Assume $ p|\frac {10^{2011} - 1}{9}$, then $ p|10^{2011} - 1$. $ p|10^{p - 1} - 1$ then $ p|10^{(p - 1,2011)} - 1$. But $ (p,9) = 1$ so $ p - 1\vdots 2011$, $ p$ odd hence $ p - 1\vdots 4022$. $ p = 4022k + 1$. Why $ p|10^{2011} - 1$ includes $ p|10^{p - 1} - 1$?
19.05.2012 22:30
a) No: the sum of its digits is a multiple of $3$, and therefore the number is divisible by $3$. b) We write the number as $\frac {10^{2011}-1} 9$; for $p \neq 3$ which divides this number, we must have $10^{2011} \equiv 1 \pmod p$, or $\text {ord}_p(10)$ divides $2011$, but since $2011$ is prime we actually get $\text{ord}_p(10)=2011$ (it cannot be $1$ since $p \neq 3$); then $2011$ divides $p-1$, and for $p$ odd, $4022$ divides $p-1$.