# Proof of the Euler Generalisation of Fermat's Little Theorem using modular arithmetic

Fermat's Little Theorem, in Fermat-Euler form, states that: if $\gcd(a,m)=1$, then $a^{\varphi(m)} \equiv 1 \pmod{m}$.

Now, I've been asked to prove it via modular arithmetic. In order to do this I understand that I'm to use two lemmas:

1. $\varphi(p^n) = p^{n} - p^{n-1}$. This I can prove by working out that there are $p^n$ numbers less than $p^n$ of which $p^{n-1}$ of them are divisible by $p$.
2. Given $gcd(r,s) = 1$, $\varphi(rs) = \varphi(r)\varphi(s)$. This I'm having problems with.

My lecturer suggested the proposition that $\varphi(n) = n\prod_{p|n}\left(1-\frac{1}{p}\right)$. I can re-arrange this to equal lemma 1, but what I can't understand how that proposition proves 2, which my lecturer claims it does, and why these two points together prove the theorem.

I suspect I might follow the argument correctly if I fully understood lemma 2.

-
For 2., $r$ and $s$ need to be relatively prime... –  Eric O. Korman Dec 12 '10 at 21:03
You have a couple of errors. First, you either should have $a^{\varphi(p)}\equiv 1\pmod{p}$ (cf. exponents) or $a^{\varphi(m)}\equiv 1 \pmod{m}$. Either way, you also need to require that $a$ be relatively prime to the modulus. Also, and more serious, is that (2) as stated is false: you need to also ask that $\gcd(r,s)=1$ (otherwise, take $r=s=p$ a prime to see it does not work). –  Arturo Magidin Dec 12 '10 at 21:08
@Arturo Sorry, my omission/typo. corrected question. –  Ninefingers Dec 12 '10 at 21:10
@Arturo The Euler generalisation. Also, not homework. We weren't asked to prove it, the lecturer's logic just makes quantum leaps I don't grasp. –  Ninefingers Dec 12 '10 at 21:16
Okay: I fixed the text, then; you had changed it to Fermat's Little Theorem instead of fixing the modulus to get Euler. –  Arturo Magidin Dec 12 '10 at 21:18

Part 2 can be proven in many different ways; what your lecturer suggests, if you already know the identity, will do it. Just notice that if $p|rs$, then either $p|r$ or $p|s$, and not both, since $\gcd(r,s)=1$. So we have: $$\varphi(rs) = rs\prod_{p|rs}\left(1 - \frac{1}{p}\right) = rs\left(\prod_{p|r}\left(1 - \frac{1}{p}\right)\right)\left(\prod_{p|s}\left(1-\frac{1}{p}\right)\right),$$ and go from there.

One you have this, the proof of the Fermat-Euler Theorem reduces to proving that if $\gcd(a,p)=1$, then $a^{\varphi(p^n)} \equiv 1 \pmod{p^n}$ for every positive integer $n$; you can use 2 and the Chinese Remainder Theorem to prove that this suffices, and then you can use 1 to try to establish the condition modulo a prime power.

-
Aaah. Now that makes sense. Thanks! –  Ninefingers Dec 12 '10 at 21:26

Here is another way to prove Euler's generalization. You do not need to know the formula of $\varphi(n)$ for this method which I think makes this method elegant.

Consider the set of all numbers less than $n$ and relatively prime to it. Let $\{a_1,a_2,...,a_{\varphi(n)}\}$ be this set.

Consider a number $c < n$ and relatively prime to it i.e. $c \in \{a_1,a_2,\ldots,a_{\varphi(n)}\}$.

First observe that for any $a_i$, $c a_{i} \equiv a_{j} (\bmod n)$ for some $j$. (True since $c$ and $a_i$ are themselves relatively prime to $n$, their product has to be relatively prime to $n$).

And if $c a_{i} \equiv c a_{j} (\bmod n)$ then $a_i = a_j$. (True as cancellation can be done since $c$ is relatively prime to $n$).

Hence, if we now consider the set $\{ca_1,ca_2,...,ca_{\varphi(n)}\}$ this is just a permutation of the set $\{a_1,a_2,...,a_{\varphi(n)}\}$.

Thereby, we have $\displaystyle \prod_{k=1}^{\varphi(n)} ca_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.

Hence, we get $\displaystyle c^{\varphi(n)} \prod_{k=1}^{\varphi(n)} a_k \equiv \prod_{k=1}^{\varphi(n)} a_k (\bmod n)$.

Now, note that $\displaystyle \prod_{k=1}^{\varphi(n)} a_k$ is relatively prime to $n$ and hence you can cancel them on both sides to get

$$c^{\varphi(n)} \equiv 1 (\bmod n)$$ whenever $(c,n) = 1$

-