Proving Euler’s Totient Theorem

I'll give you a headstart on a proof for this.

Consider a prime number $P$ with $gcd(a,P)=1$. From Fermat's Little Theorem, we know that $a^{P-1}=1+P cdot N_1$, for some positive integer $N_1$. This implies that $a^{P(P-1)}=(1+P cdot N_1)^P=1+binom{P}{1} cdot P cdot N_1+binom{P}{2}+(P cdot N_1)^2...+binom{P}{P} cdot (P cdot N_1)^P$. This implies that $a^{P(P-1)}=1+p^2 cdot N_2$, for some positive integer $N_2$. Similarly, by a simple induction, we get $A^{P^{k-1} cdot (P-1)}=1+p^k cdot N_k$, for some positive integer $N_k$.

Try to continue.

Hope this helped!

I'll try to give you a loose proof, assuming you know some things about modular arithmetic, and hopefully you can flesh out the details yourself. I've adapted this mostly from Brilliant.org.

Let's start with modular multiplication. In general, it's not always possible to solve the relation:

$$ a times k equiv bspace (textrm{mod}space n) $$

for $k$ when you know $a$, $b$, and $n$. For example consider the situation where $a = 6$, $b=2$, and $n = 15$. Try as you might, you will not be able to find a $k$ between $0$ and $14$ that satisfies that relation.

In normal arithmetic, what we would do is multiply by the multiplicative inverse of $a$ (i.e. the number $a^{-1}$ such that $a^{-1}times a = 1$, or in this case, $a^{-1}times a equiv 1space (textrm{mod}space n)$) on both sides to find $k$. In modular arithmetic, $a$ has a multiplicative inverse if and only if $a$ is relatively prime to $n$. (Can you see why? Additive cycles in modular arithmetic might be useful.)

Now let's go to repeated multiplication in modular arithmetic. If you start with some integer $m$ and repeatedly multiply it by some factor $k$ some number of times $textrm{mod} space n$, you will eventually end up in a multiplicative cycle. The cycle will only include the first repeat and the integers that appear after it. There are usually multiple multiplicative cycles for each choice of $n$ and $k$, and all of them together contain each integer from $0$ to $n-1$ once and only once. An example for 4 modulo 14

Let's examine the case of starting at $1$ and repeatedly multiplying by $2$ modulo $20$. This generates the sequence $1, 2, 4, 8, 16, 12, 4, 8, 16, 12, 4, ldots$

Notice there is more than one integer that leads to $4$ when multiplying by $2$ in this sequence, namely $2$ and $12$. There is a "tail" which includes $1$ and $2$ before coming to our cycle.

However, if we are instead multiplying by some integer $a$ that is relatively prime to $20$ i.e. has a multiplicative inverse $textrm{mod} space 20$, this can't happen. That means that all the multiplicative cycles containing integers relatively prime to $n$ don't have any "tails" like the given example or the earlier example of 4 modulo 14. The existence of the inverse implies reversibility which forbids two separate numbers multiplying to the same number. (Try it out!)

Also notice that this reversibility implies the cycle containing $a$ also contains $1$. We are now getting tantalizingly close to Euler's totient theorem.

Notice that all the multiplicative cycles containing integers relatively prime to $n$ are of the same length. If every integer in the cycle contains a multiplicative inverse, they can all be multiplied by some constant to obtain another cycle of the same length. An example for 3 modulo 16

Finally, we get to the crux of the argument. The length of these cycles is a divisor of $phi(n)$ (Can you see why?). If we call this length $l$ and the total number of these cycles $c$, then

$$ a^lequiv a^0equiv 1 space (textrm{mod} space n) $$

and

$$ ltimes c = phi(n) $$

and finally

$$ a^{phi(n)} = a^{ltimes c} = ({a^l})^c equiv 1^c (textrm{mod} space n) equiv 1(textrm{mod} space n) $$

$(mathbb{Z}/n)^times$ is a group, where Lagrange theorem can be applied. Therefore, if $a$ and $n$ are coprime (which is needed), then $a$ is invertible in the ring $mathbb{Z}/n$, i.e. : $$a^{#(mathbb{Z}/n)^times}=a^{varphi(n)}=1.$$

---

Proof : $#(mathbb{Z}/n)^times=varphi(n)$.

$ainmathbb{Z}/n$ is invertible

$iff$ $akequiv 1;;(text{mod };n)$ for some $k$

$iff$ $ak+nu=1$ for some $k,u$

$iff$ $text{GCD}(a,n)=1$ from Bézout.

Therefore : $$(mathbb{Z}/n)^times={ain[![1,n]!],;/;text{GCD}(a,n)=1},$$

from which we get the announced property, from the definition for $varphi$. $qquadblacksquare$