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{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\]
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{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\)