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 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
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
Maybe he wanted to say the following :
For any prime there's a number of the form which is divisible by (in fact there are infinitely many)
I'll post 2 proofs.
1) By the pidgeon-hole principle (or Dirichlet's principle)
Consider ; ; ...;
Since there are p remainders when dividing by , and we have got p+1 numbers , 2 of these numbers, at least, must be leave the same remainder, hence for some
But: thus: but since 10 is coprime to p it must be that
( As a side comment, it's enough to take 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: hence
Now by Fermat's Little Theorem we have: and the rest follows. In fact we have shown that, if p is a prime and