Euler’s Little Theorem (Bonus Proof)

For those who followed the Newbie as Number Theory series, you would have already seen both Fermat’s Little Theorem and what I dubbed Euler’s Little Theorem. The proof we gave in the article about Euler’s little theorem did not rely on Fermat’s little theorem. However, it’s anyways fun to try to prove old things in new ways. Today, we will give another proof that does use Fermat’s Little Theorem!

But to make sure we are all on the same page:

Fermat’s Little Theorem: Let be prime and let then

Euler’s Little Theorem: Let and be a positive integers such that then

where is Euler’s totient function.

Proof: The effort is showing that Fermat’s Little Theorem implies Euler’s Little Theorem. For this reason, we focus on this direction of the proof.

Let Fermat’s Little Theorem hold for all prime and integers where .

Consider some natural numbers $n$ and $a$ such that . We are aiming to show . In the case that is prime we uses Fermat’s Little Theorem and we are done. So, let’s assume that is composite (we disregard the case ). Therefore, factors uniquely into distinct primes (by the Fundamental Theorem of Arithmetic):

$n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$

for primes and .

In order to show this for any composite number, we will use induction on $r$ .

Base Case: Consider some prime $p$ . We will show that,

$a^{\phi(p^{k})} \equiv 1\pmod{p^{k}}$

for all $k\in \mathbb{N}$ . We do this using induction on $k$ . Our base case is simply Fermat’s Little Theorem.

Assume that $a^{\phi(p^{k})} \equiv 1\pmod{p^{k}}$ for some $k$ . We will show that $a^{\phi(p^{k+1})} \equiv 1\pmod{p^{k+1}}$ . To this end, observe

$\phi(p^{k+1}) = p^{k+1} - p^{k} \\ \textit{ }\qquad\;\;\;=p \, \phi(p^k).$

Using the binomial theorem, our induction hypothesis, and the above result we deduce,

$a^{\phi(p^{k+1})} = (a^{\phi(p^k)})^p = (p^km +1)^p\\ \\ \textit{ }\qquad \;\;= \sum_{i=0}^p \binom{p}{i} (p^k m)^i\\ \\ \textit{ }\qquad\;\;= 1 + p^{k}m \Bigg(\sum_{i=1}^p \binom{p}{i} (p^{k} m)^{i-1}\Bigg) \\ \\ \textit{ }\qquad \;\;\equiv 1 \pmod{p^{k+1}}.$

Observe that $\sum_{i=1}^p \binom{p}{i} (p^{k} m)^{i-1} \in \mathbb{Z}$ which completes our induction and the base case.

Warm Up: Here we will do a quick warm up for our induction step. We do the case when $r=2$ .

Let $p$ and $q$ be distinct primes and let $k,t\in \mathbb{N}$ . We will show $a^{\phi(p^k)\phi(q^t)} \equiv 1\pmod{p^kq^t}$ . To this end, note that

$a^{\phi(p^{k})\phi(q^t)} \equiv 1 \pmod{p^{k}} \qquad \mathrm{and} \qquad a^{\phi(p^{k})\phi(q^t)} \equiv 1 \pmod{q^{t}}$

Equivalently,

$a^{\phi(p^{k})\phi(q^t)} - 1 = p^{k}\alpha \qquad \mathrm{and} \qquad a^{\phi(p^{k})\phi(q^t)} - 1 = q^{t}\beta. \\ \textit{ }\qquad\qquad$

Where $\alpha,\beta\in\mathbb{Z}$ . Thus,

$p^{k}\alpha = q^{t}\beta .$

Which, by Euclid’s lemma, we deduce $p^k\mid \beta.$ Hence,

$a^{\phi(p^{k})\phi(q^t)} - 1 = p^{k}q^{t}\gamma. % a^{\phi(p^{k})\phi(q^t)} - 1 = q^{t}\beta.$

for some $\gamma\in\mathbb{Z}$ . Therefore,

$a^{\phi(p^k)\phi(q^t)} \equiv 1\pmod{p^kq^t}$

Finishing our warm up. We will do the exact same series of steps, but with more primes!

Induction Step: Assume that $a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})} \equiv 1\pmod{p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r}}$ for some $r$ . By our induction hypothesis,

$a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})\phi(p_{r+1}^{k_{r+1}})} = \Big(a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})} \Big)^{\phi(p_{r+1}^{k_{r+1}})} \equiv 1\pmod{p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r}}$

and

$a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})\phi(p_{r+1}^{k_{r+1}})} = \Big(a^{\phi(p_{r+1}^{k_{r+1}})}\Big)^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})} \equiv 1 \pmod{p_{r+1}^{k_{r+1}}} .$

Equivalently,

$a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})\phi(p_{r+1}^{k_{r+1}})} -1= (p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r}) \alpha$

and

$a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})\phi(p_{r+1}^{k_{r+1}})} -1= p_{r+1}^{k_{r+1}}\beta$

Where $\alpha,\beta\in\mathbb{Z}$ . Thus,

$(p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r})\alpha = p_{r+1}^{k_{r+1}}\beta \ \textit{ }\qquad\qquad$

and by Euclid’s lemma $p_{i}^{k_{i}}\mid \beta$ for all $1\leq i \leq r$ (or simply that $p_{r+1}^{k_{r+1}}\mid \alpha$ ) so that,

$a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})\phi(p_{r+1}^{k_{r+1}})} - 1=p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r} p_{r+1}^{k_{r+1}}\gamma$

for some $\gamma\in\mathbb{Z}$ . Therefore,

$a^{\phi(p_1^{k_1})\phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})\phi(p_{r+1}^{k_{r+1}})} \equiv 1\pmod{p_1^{k_1} p_2^{k_2}\cdots p_r^{k_r} p_{r+1}^{k_{r+1}}}$

Comleting the induction.

$\square$

Closing Remarks

Today was a fresh take on something old. However, I hope you found it interesting! There was a lot of algebra, binomials, exponents, etc. How awesome!

As always, thank you for taking the time to read this article! I appreciate it!

A Kick in the Discovery