# Euler's Theorem

**Euler's theorem** is a generalization of Fermat's little theorem dealing with powers of integers modulo positive integers. It arises in applications of elementary number theory, including the theoretical underpinning for the RSA cryptosystem.

Let $n$ be a positive integer, and let $a$ be an integer that is relatively prime to $n.$ Then

$a^{\phi(n)} \equiv 1 \pmod n,$

where $\phi(n)$ is Euler's totient function, which counts the number of positive integers $\le n$ which are relatively prime to $n.$

Suppose $a$ is relatively prime to $10.$ Since $\phi(10)=4,$ Euler's theorem says that $a^4 \equiv 1 \pmod{10},$ i.e. the units digit of $a^4$ is always $1.$ See the wiki on finding the last digit of a power for similar problems.

#### Contents

## Proofs of the Theorem

Here are two proofs: one uses a direct argument involving multiplying all the elements together, and the other uses group theory.

Proof using residue classes:Consider the elements $r_1, r_2, \ldots, r_{\phi(n)}$ of $({\mathbb Z}/n)^*,$ the congruence classes of integers that are relatively prime to $n.$ For $a\in ({\mathbb Z}/n)^*,$ the claim is that multiplication by $a$ is a permutation of this set; that is, the set $\{ ar_1, ar_2, \ldots, ar_{\phi(n)} \}$ equals $({\mathbb Z}/n)^*.$ The claim is true because multiplication by $a$ is a function from the finite set $({\mathbb Z}/n)^*$ to itself that has an inverse, namely multiplication by $\frac1a \pmod n.$

For example, let $n=9$ and $a=2.$ Then $({\mathbb Z}/n)^* = \{ 1,2,4,5,7,8\}.$ Multiplication by $2$ turns this set into $\{2,4,8,1,5,7\}.$ So it permutes the elements of the set.

$\big($Multiplication by $5 = \frac12 \pmod 9$ is the inverse of this permutation.$\big)$Now, given the claim, consider the product of all the elements of $({\mathbb Z}/n)^*.$ On one hand, it is $r_1r_2\cdots r_{\phi(n)}.$ On the other hand, it is $(ar_1)(ar_2)(\cdots)(ar_{\phi(n)}).$ So these products are congruent mod $n$:

$\begin{aligned} r_1r_2\cdots r_{\phi(n)} &\equiv (ar_1)(ar_2)(\cdots)(ar_{\phi(n)}) \\ r_1r_2\cdots r_{\phi(n)} &\equiv a^{\phi(n)} r_1r_2\cdots r_{\phi(n)} \\ 1 &\equiv a^{\phi(n)}, \end{aligned}$

where cancellation of the $r_i$ is allowed because they all have multiplicative inverses $\pmod n.$ $_\square$

Proof using Lagrange's theorem:The elements in $({\mathbb Z}/n)$ with multiplicative inverses form a group under multiplication, denoted $({\mathbb Z}/n)^*$. This group has $\phi(n)$ elements. The subgroup consisting of the powers of $a$ has $d$ elements, where $d$ is the multiplicative order of $a$ $\big($because the elements of the subgroup are $1,a,a^2,\ldots,a^{d-1}\big).$

By Lagrange's theorem, $d|\phi(n),$ say $dk=\phi(n)$ for some integer $k.$ Since $a^d\equiv 1\pmod{n},$

$a^{\phi(n)} \equiv a^{dk} \equiv \left( a^d \right)^k \equiv 1^k \equiv 1 \pmod{n}.\ _\square$

## Applications

Show that if $n$ is an odd integer, then $n$ divides $2^{(n-1)!} -1$.

The statement is clear for $n=1,$ so assume $n>1.$ By Euler's theorem, $2^{\phi(n)} \equiv 1 \pmod n$. Since $\phi(n) \le n-1$, we have $(n-1)! = \phi(n) \cdot k$ for some integer $k$. So

$2^{(n-1)!} \equiv 2^{\phi(n) \cdot k} \equiv \left(2^{\phi(n)}\right)^k \equiv 1^k \equiv 1 \pmod n.\ _\square$

An army of worker ants was carrying sugar cubes back into their colony. In there, the ants put 1 sugar cube into the first room, 2 into the second, 4 into the third, and doubling the amount so on until the $101^\text{th}$ room.

Then the queen ant decided to build bigger cubic blocks of $5\times 5\times 5$ sugar cubes from all they had previously collected. How many sugar cubes would remain after all these build-ups?

Let $a_1 = 3$ and $a_n = 3^{a_{n-1}}$ for $n \ge 2.$ Find the last two digits of $a_{2016}.$

Note that $a_k \equiv 3$ mod $4$ for all $k.$ Now the goal is to compute $a_{2016} \pmod{25}.$ Since $a_{2016} = 3^{a_{2015}},$ it suffices to compute $a_{2015}$ mod $\phi(25) = 20.$ Similarly, we want $a_{2014}$ mod $\phi(20)=8,$ $a_{2013}$ mod $\phi(8)=4,$ and $a_{2012}$ mod $\phi(4)=2.$ But all the $a_k$ are odd, so $a_{2012} \equiv 1 \pmod 2.$ Working our way back up,

$\begin{aligned} a_{2013} \equiv 3^1 &\equiv 3 \pmod 4 \\ a_{2014} \equiv 3^3 &\equiv 3 \pmod 8 \\ a_{2015} \equiv 3^3 &\equiv 7 \pmod{20} \\ a_{2016} \equiv 3^7 &\equiv 12 \pmod{25}. \end{aligned}$

So $a_{2016} \equiv 3 \pmod 4$ and $a_{2016} \equiv 12 \pmod{25},$ so by the Chinese remainder theorem it is congruent to a unique element mod $100,$ which is $87$ by inspection. $_\square$