Section 6.3 Fermat's and Euler's Theorems
The Euler \(\phi\)-function is the map \(\phi : {\mathbb N } \rightarrow {\mathbb N}\) defined by \(\phi(n) = 1\) for \(n=1\text{,}\) and, for \(n \gt 1\text{,}\) \(\phi(n)\) is the number of positive integers \(m\) with \(1 \leq m \lt n\) and \(\gcd(m,n) = 1\text{.}\)
From Proposition 3.4, we know that the order of \(U(n)\text{,}\) the group of units in \({\mathbb Z}_n\text{,}\) is \(\phi(n)\text{.}\) For example, \(|U(12)| = \phi(12) = 4\) since the numbers that are relatively prime to 12 are 1, 5, 7, and 11. For any prime \(p\text{,}\) \(\phi(p) = p-1\text{.}\) We state these results in the following theorem.
Theorem 6.17.
Let \(U(n)\) be the group of units in \({\mathbb Z}_n\text{.}\) Then \(|U(n)| = \phi(n)\text{.}\)
The following theorem is an important result in number theory, due to Leonhard Euler.
Theorem 6.18. Euler's Theorem.
Let \(a\) and \(n\) be integers such that \(n \gt 0\) and \(\gcd(a, n) = 1\text{.}\) Then \(a^{\phi(n)} \equiv 1 \pmod{n}\text{.}\)
Proof.
By Theorem 6.17 the order of \(U(n)\) is \(\phi(n)\text{.}\) Consequently, \(a^{\phi(n)} = 1\) for all \(a \in U(n)\text{;}\) or \(a^{\phi(n)} - 1\) is divisible by \(n\text{.}\) Therefore, \(a^{\phi(n)} \equiv 1 \pmod{n}\text{.}\)
If we consider the special case of Euler's Theorem in which \(n = p\) is prime and recall that \(\phi(p) = p - 1\text{,}\) we obtain the following result, due to Pierre de Fermat.
Theorem 6.19. Fermat's Little Theorem.
Let \(p\) be any prime number and suppose that \(p \notdivide a\) (\(p\) does not divide \(a\)). Then
Furthermore, for any integer \(b\text{,}\) \(b^p \equiv b \pmod{ p}\text{.}\)
Subsection Historical Note
Joseph-Louis Lagrange (1736–1813), born in Turin, Italy, was of French and Italian descent. His talent for mathematics became apparent at an early age. Leonhard Euler recognized Lagrange's abilities when Lagrange, who was only 19, communicated to Euler some work that he had done in the calculus of variations. That year he was also named a professor at the Royal Artillery School in Turin. At the age of 23 he joined the Berlin Academy. Frederick the Great had written to Lagrange proclaiming that the “greatest king in Europe” should have the “greatest mathematician in Europe” at his court. For 20 years Lagrange held the position vacated by his mentor, Euler. His works include contributions to number theory, group theory, physics and mechanics, the calculus of variations, the theory of equations, and differential equations. Along with Laplace and Lavoisier, Lagrange was one of the people responsible for designing the metric system. During his life Lagrange profoundly influenced the development of mathematics, leaving much to the next generation of mathematicians in the form of examples and new problems to be solved.