# Euler Function Proof

• Feb 4th 2011, 07: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, 07: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 $\displaystyle (a-1,m)=1$. Then, $\displaystyle a-1\in \mathbb{Z}_m^{\times}$. But, note that by using the common formula $\displaystyle \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 $\displaystyle (a-1)^{-1}$ gives the result.
• Feb 5th 2011, 12: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 $\displaystyle (a(a-1),m)=1$ implies both $\displaystyle (a,m)=1$ and $\displaystyle (a-1,m)=1$. So by Euler's Theorem, $\displaystyle a^{\phi(m)}\equiv1\pmod m$, i.e. $\displaystyle a^{\phi(m)}-1\equiv0\pmod m$.

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

But $\displaystyle \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 $\displaystyle (a-1,m)$, simply because $\displaystyle (a,m)=1$ is needed to conclude that $\displaystyle a^{\phi(m)}-1\equiv0\pmod m$.
• Feb 5th 2011, 12:04 AM
Drexel28
Quote:

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

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

But $\displaystyle \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 $\displaystyle (a-1,m)$, simply because $\displaystyle (a,m)=1$ is needed to conclude that $\displaystyle a^{\phi(m)}-1\equiv0\pmod m$.

Bleh, of course. Stupid mistake.