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{align} 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{align}\]

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{align} 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{align}\]

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