# Proving Euler’s Totient Theorem

Mathematics Asked on January 5, 2022

I’m trying to self-learn some number theory. Currently, I’m trying to prove Euler’s Totient Theorem (that is, $$a^{varphi(n)} equiv 1 pmod{n}$$ for $$a,ninmathbb{Z}$$, where $$varphi$$ denotes Euler’s Totient Function.

Unfortunately, I’m not sure where to start. I’ve tried a few different things, but I haven’t gotten very far. They’re all (seemingly) dead ends. Any hints or good starting points?

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!

Answered by OlympusHero on January 5, 2022

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

Answered by Subhasish Mukherjee on January 5, 2022

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

Answered by Anthony Saint-Criq on January 5, 2022

## Related Questions

### How to check if two functions only touch in one point?

3  Asked on December 13, 2021

### $ker(T)^{bot} = overline{im(T^*)}$ if $T$ is a linear operator between Hilbert spaces

1  Asked on December 13, 2021 by rino

### Partial Fraction Decomposition of $frac{1}{x^2(x^2+25)}$

2  Asked on December 13, 2021 by mjoseph

### How to project (draw) a rectangle on an incline plane

1  Asked on December 13, 2021 by alexander-cska

### How to find a basis of complementary subspace of a subspace not in $mathbb R^n$?

1  Asked on December 13, 2021 by jon-g

### Equality of ideals in $mathbb{Z}[sqrt{-7}]$

1  Asked on December 13, 2021

### An orthonormal basis in a subspace.

1  Asked on December 13, 2021 by ryuta-osawa

### Is there a simple-ish function for modeling seasonal changes to day/night duration and height of the sun?

3  Asked on December 13, 2021 by saganritual

### Parallel transport on the Stiefel manifold

1  Asked on December 10, 2021 by gcc

### Remainder when $^{40}C_{12}$ is divided by $7$.

2  Asked on December 10, 2021 by yash-bhatia

### Showing that for some group it is abelian iff $x • (y • x ^{−1} ) = y$

2  Asked on December 10, 2021 by cheese12345

### Summation involving Gamma function

1  Asked on December 10, 2021 by paranoid

### Probability one random variable is less than another random variable but higher than the same other random variable with a factor

1  Asked on December 10, 2021 by sottoj

### Find x in a multiple arithmetic sequence

1  Asked on December 10, 2021 by billy-senders

### Proof that this is a Primitive Recursive function

2  Asked on December 10, 2021 by user6767509

### Convergence and absolute convergence of an infinite product of terms in $(0,1]$.

1  Asked on December 10, 2021 by lce

### Describing the set ${nin Bbb Nlvert (n>1)wedge (forall x,yin Bbb N)[(xy=n)implies (x=1lor y=1)]}$

2  Asked on December 10, 2021

### What is the permutation of choosing the just 3 balls in a pool of 16 balls?

1  Asked on December 10, 2021 by mahesh87

### Determine number of divisors of $x^n -1$ of degree $k$. Why are they such a number?

1  Asked on December 10, 2021

### why does a set of parametric equations need to be smooth and not cross itself in order to evaluate its arc length?

0  Asked on December 10, 2021 by lightbulb