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.

Compute the last two digits of $79^{79}$ .

The correct answer is: 19

Solution 1: It is not hard to find high powers of $79$ modulo $100$ by repeated squaring. The following calculations can be easily done by hand using standard multiplication procedure, cut off at two digits.

$79^2 \equiv 41 \pmod {100}$ , $79^4\equiv 41^2 \equiv 81 \pmod{100},$ $79^8\equiv 81^2 \equiv 61 \pmod {100},$ $79^{16}\equiv 61^2 \equiv 21 \pmod {100},$ $79^{32}\equiv 21^2 \equiv 41\pmod {100},$ $79^{64}\equiv 41^2 \equiv 81 \pmod{100}.$

Because $79=64+15,$ $79^{79}\equiv 79^{64}\cdot 79^{15} \pmod {100}.$ To find $79^{15},$ we can first find $79^5=79^4\cdot 79\equiv 81 \cdot 79 \equiv 99 \equiv -1 \pmod{100}.$ Then $79^{15}\equiv (-1)^3\equiv -1 \pmod {100}$ and $79^{79}\equiv 81 \cdot (-1) \equiv 19 \pmod {100},$ so the answer is $19.$

For the following solutions let $\phi(N)$ be the number of integers less than $N$ that are coprime to $N$ (also known as Euler's Totient function). If $N = p_1^{q_1} p_2^{q_2} \ldots p_n^{q_n}$ then $\phi(N) = N\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\ldots \left(1 - \frac{1}{p_n}\right)$ .

Solution 2: Since $\phi(100) = 100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right) = 40$ , thus $79^{79} \equiv 79^{-1}\cdot 79^{40\cdot 2} \equiv 79^{-1} \pmod{100}$ by Euler’s Theorem. Since $\gcd(79,100) = 1$ , thus a multiplicative inverse exists. We can calculate the inverse using the Euclidean Algorithm and get that:

$\begin{array}{1,1} 100 &=& 79\times 1 + 21 \\ 79 &=& 21\times 3 + 16 \\ 21 &=& 16\times 1 + 5 \\ 16 &=& 5\times 3 + 1 \end{array}$

Thus, the above shows that $\gcd(79,100) = 1$ and we can calculate the inverse as follows:

$\begin{array}{1,1} 1 & = & 16 - 5\times 3 \\ & = & 16 - (21-16\times 1)\times 3 \\ & = & 16\times 4 - 21\times 3 \\ & = & (79 - 21\times 3)\times 4 - 21\times 3 \\ & = & 79\times 4 - 21\times 15 \\ & = & 79\times 4 - (100-79)\times 15 \\ & = & 79\times 19 - 100\times 15 \end{array}$

So we have, $1 \equiv 79\times 19 \pmod{100}$ $\Rightarrow 79^{-1} \pmod{100} = 19 \pmod{100}$ .

Solution 3: Since $\gcd(79, 100) = 1$ and $\phi(4)= 4\left(1-\frac{1}{2}\right) = 2$ , thus $79^{79} \equiv 3^1 \equiv 3 \pmod{4}$ . Since $\phi(25) = 25(1 - \frac{1}{5}) = 20$ , thus $79^{79} \equiv 4^{19} \equiv 4^{4\times4+3} \equiv 256^4 \times 64 \equiv 6^4 \times 14 \equiv 19 \pmod{25}$ . Since $19 \equiv 3 \pmod{4}$ , thus $79^{79} \equiv 19 \pmod{100}$ .

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$

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$

Contents