# Thread: Euler Function Proof

1. ## Euler Function Proof

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.

2. Originally Posted by uberbandgeek6
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.
I assume it's supposed to be that $(a-1,m)=1$. Then, $a-1\in \mathbb{Z}_m^{\times}$. But, note that by using the common formula $\displaystyle (a-1)\sum_{n=0}^{\varphi(m)-1}a^n=a^\varphi(n)-1\equiv 0\text{ mod }m$. Thus, multiplying both sides by $(a-1)^{-1}$ gives the result.

3. Originally Posted by uberbandgeek6
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 $(a(a-1),m)=1$ implies both $(a,m)=1$ and $(a-1,m)=1$. So by Euler's Theorem, $a^{\phi(m)}\equiv1\pmod m$, i.e. $a^{\phi(m)}-1\equiv0\pmod m$.

Now, we can divide both sides by $a-1$ to get the equivalent congruence $\displaystyle\frac{a^{\phi(m)}-1}{a-1}\equiv0\pmod m$ since $a-1$ is relatively prime to $m$. (The left-hand side is an integer...)

But $\displaystyle\frac{a^{\phi(m)}-1}{a-1}= 1+a+a^2+\cdots+a^{\phi(m)-1}$ (Sum of geometric series). The result follows.

To Drexel28, it's not enough to have $(a-1,m)$, simply because $(a,m)=1$ is needed to conclude that $a^{\phi(m)}-1\equiv0\pmod m$.

4. Originally Posted by melese
The assumption $(a(a-1),m)=1$ implies both $(a,m)=1$ and $(a-1,m)=1$. So by Euler's Theorem, $a^{\phi(m)}\equiv1\pmod m$, i.e. $a^{\phi(m)}-1\equiv0\pmod m$.

Now, we can divide both sides by $a-1$ to get the equivalent congruence $\displaystyle\frac{a^{\phi(m)}-1}{a-1}\equiv0\pmod m$ since $a-1$ is relatively prime to $m$. (The left-hand side is an integer...)

But $\displaystyle\frac{a^{\phi(m)}-1}{a-1}= 1+a+a^2+\cdots+a^{\phi(m)-1}$ (Sum of geometric series). The result follows.

To Drexel28, it's not enough to have $(a-1,m)$, simply because $(a,m)=1$ is needed to conclude that $a^{\phi(m)}-1\equiv0\pmod m$.
Bleh, of course. Stupid mistake.