# Euler Function Proof

• Feb 4th 2011, 08:09 PM
uberbandgeek6
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.
• Feb 4th 2011, 08:18 PM
Drexel28
Quote:

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.
• Feb 5th 2011, 01:02 AM
melese
Quote:

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$.
• Feb 5th 2011, 01:04 AM
Drexel28
Quote:

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.