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