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.

I have been stuck on this exercise for far too long:

Show that if $a$ and $m$ are positive integers with $(a,b)=(a-1,m)=1$, then $$1+a+a^2+\cdots+a^{\phi(m)-1}\equiv0\pmod m.$$

First of all, I know that $$1+a+a^2+\cdots+a^{\phi(m)-1}=\frac{a^{\phi(m)-2}-1}{a-1},$$ and by Euler's theorem, $$a^{\phi(m)}\equiv1\pmod m.$$ Now, because $(a,m)=1$, we have $$a^{\phi(m)-2}\equiv a^{-2}\pmod m,$$ $$a^{\phi(m)-2}-1\equiv a^{-2}-1\pmod m,$$ and because $(a-1,m)=1$, $$\frac{a^{\phi(m)-2}-1}{a-1}\equiv\frac{a^{-2}-1}{a-1}\pmod m,$$ $$1+a+a^2+\cdots+a^{\phi(m)-1}\equiv\frac{a^{-2}-1}{a-1}\pmod m.$$ However, I get stuck here. Is there a way to show that the RHS of that last expression is congruent to zero modulus $m$? Thanks in advance!

Note: I really do not know if I am tackling this problem correctly to begin with.

share|improve this question
7  
I think your first formula is wrong: $1+a+a^2+\cdots+a^k = \frac{a^{k+1}-1}{a-1}$; so the exponent on the right hand side should not be $\phi(m)-2$, it should be $\phi(m)$. –  Arturo Magidin Mar 6 '12 at 20:40
    
That's where I went wrong... oh, my. Where do I hide my face. Thank you very much, @ArturoMagidin. The solution now follows easily. –  Josué Molina Mar 6 '12 at 20:43
    
I suggest posting an answer noting the error, and then your solution; that way (i) people can comment on your write-up; (ii) the question won't go unanswered; and (iii) Everntually, you can even accept your own answer! –  Arturo Magidin Mar 6 '12 at 20:54
4  
As a small matter. I would prefer to write $(1+a+\cdots +a^{\varphi(m)-1})(1-a)=1-a^{\varphi(m)}$ (so no division). –  André Nicolas Mar 6 '12 at 20:55

1 Answer 1

up vote 1 down vote accepted

Hint: From $a^{\phi(m)}-1$ is congruent to 0 mod m and is congruent to the $(a^{\phi(m)}-1)/(a-1)$ mod m

share|improve this answer

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.