Euler Function Proof

**uberbandgeek6** · February 4th 2011, 07:09 PM

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.

**Drexel28** · February 4th 2011, 07:18 PM

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.

**melese** · February 5th 2011, 12:02 AM

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$ .

**Drexel28** · February 5th 2011, 12:04 AM

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.

Thread: Euler Function Proof

LinkBack

Thread Tools

Display

Euler Function Proof

Similar Math Help Forum Discussions

[SOLVED] Euler function proof

Euler's totient function Proof

Proof about Euler's φ-function

Euler's phi function proof

Euler phi function proof

Search Tags