Suppose that m is an integer with m > 1 and gcd(a(a-1), m) = 1. Prove that:
1 + a + a^2 + ... + a^(phi(m) - 1) ≡ 0 mod m
I'm really not sure where to start with this. I assume I will have to make use of Euler's Theorem at some point, but I don't even know where to begin.
The assumption implies both and . So by Euler's Theorem, , i.e. .
Now, we can divide both sides by to get the equivalent congruence since is relatively prime to . (The left-hand side is an integer...)
But (Sum of geometric series). The result follows.
To Drexel28, it's not enough to have , simply because is needed to conclude that .