Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the shortest proof to show $\underbrace{{111\cdots}1}_{{\small{p-1} \ 1's}}$ is divisible by $p$

share|improve this question
    
Try looking up Fermats little Theorem –  Kirthi Raman Mar 24 '12 at 2:59
3  
As noted in comments to KV Raman's answer, this is false for $p=2,3,5$. (But true for all other $p$.) –  alex.jordan Mar 24 '12 at 3:08
3  
In base $b,$ this will be false for any primes that divide either $b$ or $b-1.$ –  user2468 Mar 24 '12 at 3:09
    
When I looked back my notes, I missed the point $p \geq 7$, and it is all my fault. –  Kirthi Raman Mar 25 '12 at 0:11
add comment

1 Answer

up vote 9 down vote accepted

$$\underbrace{{111\cdots}1}_{{\small{p-1} \ 1's}} = \frac{10^{p-\small{1}}-1}{9} \equiv 0 \pmod{p}$$

because by Fermats little theorem, since gcd$(10,p)=1, 10^{p-1} \equiv 1 \pmod{p}$

NOTE: Assuming $p > 5$. The result is not true for $p=2, 3$ or $5$. In all the excitement to show, I missed important point.

For $p=2$ obviously $1$ is not divisible by $2$ - does not hold, and $p=3$, $11$ is not divisible by $3$ and finally for $p=5$ gcd$(5,10)=2$ and therefore not true as well ($1111$ is not divisible by $5$).

share|improve this answer
1  
For completeness, consider the cases p=2,5 as well. (gcd(10, p) is not 1 in these cases) –  Jan Gorzny Mar 24 '12 at 3:03
    
How is $\gcd(10, p) = 1$? Are you assuming either $p \neq 2, 5$ or $p \ge 11$? –  user2468 Mar 24 '12 at 3:04
    
Ops. Posted same comment as Jan Grozny. –  user2468 Mar 24 '12 at 3:05
2  
Also, the whole thing is false for $p=3$ due to that division by $9$. –  alex.jordan Mar 24 '12 at 3:06
    
@alex.jordan good catch –  Jan Gorzny Mar 24 '12 at 3:09
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.