5
$\begingroup$

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.

  • 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)$.2012-03-06
  • 0
    That's where I went wrong... oh, my. Where do I hide my face. Thank you very much, @ArturoMagidin. The solution now follows easily.2012-03-06
  • 0
    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!2012-03-06
  • 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).2012-03-06

1 Answers 1

0

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