# Math Help - interesting question

1. ## interesting question

Prove that any number of the form 111...111 (k decimal places) is divisible by an prime p, where p cannot equal 5. Thanks for the help.

2. Originally Posted by htata123
Prove that any number of the form 111...111 (k decimal places) is divisible by an prime p, where p cannot equal 5. Thanks for the help.
I'm not sure what you are trying to prove. If it is that 111...111 is divisible by any prime other than 5,that's simply not true- there exist primes larger than that number itself! And, of course, 11 and 111 are themselves prime. It is trivial to prove that such a number is not divisible by 5. What, exactly, is it that you are trying to prove?

3. I'm trying to prove that a number of the form 111....111 is divisible by any prime other than 5. I admit there are prime numbers greater than 111....111 but there is also a number 111.....111 which is greater than that prime. I got this question from one of the text books on number theory but can't seem to find an answer

4. May be I don't understand your question but your number 1..11 must have some prime factors (fundamental theorem of arithmetic) and any of them are different from 5 (multiples of 5 are equal to 0 or 5 modulo 10). Also for 11, the only prime which divide it is itself

5. It is still not true. For example 2 is a prime number. Do you think it divides 111...111?

6. Maybe he wanted to say the following :

For any prime $p>5$ there's a number of the form $11...1$ which is divisible by $p$ (in fact there are infinitely many)

I'll post 2 proofs.

1) By the pidgeon-hole principle (or Dirichlet's principle)

Consider $1$; $11$; ...; $
\underbrace {11...1}_{p+1 {\text{ 1's}}}
$

Since there are p remainders when dividing by $p$, and we have got p+1 numbers , 2 of these numbers, at least, must be leave the same remainder, hence $
\underbrace {11...1}_{k{\text{ 1's}}} - \underbrace {11...1}_{j{\text{ 1's}}} = \dot p
$
for some $p+2>k>j>0$

But: $
\underbrace {11...1}_{k{\text{ 1's}}} - \underbrace {11...1}_{j{\text{ 1's}}} = \underbrace {11...1}_{k - j{\text{ 1's}}}\underbrace {0...0}_{j{\text{ 0's}}} = 10^j \cdot \underbrace {11...1}_{k - j{\text{ 1's}}}
$
thus: $
p\left| {\left( {10^j \cdot \underbrace {11...1}_{k - j{\text{ 1's}}}} \right)} \right.
$
but since 10 is coprime to p it must be that $
p\left| {\underbrace {11...1}_{k - j{\text{ 1's}}}} \right.
$

( As a side comment, it's enough to take $p$ numbers, the reasoning would be, if any of the given numbers is multiple of p we are done, so suppose the contrary, then we have p-1 possible remainders and p numbers... and we get a contradiction )

2) Note that: $
\underbrace {11...1}_{n{\text{ 1's}}} = \tfrac{{10^n - 1}}
{9}
$
hence $
p\left| {\underbrace {11...1}_{n{\text{ 1's}}}} \right.\underbrace \Leftrightarrow _{{\text{by (H) }}p > 5 \Rightarrow p \ne 3}p\left| {\left( {10^n - 1} \right)} \right.
$

Now by Fermat's Little Theorem we have: $
\left( {10;p} \right) = 1 \Rightarrow 10^{p - 1} \equiv 1\left( {\bmod .p} \right)
$
and the rest follows. In fact we have shown that, if p is a prime and $
p > 5 \Rightarrow p\left| {\underbrace {11...1}_{p - 1{\text{ 1's}}}} \right.
$

7. The second proof was the proof my professor gave me. thanks for your reply.