Euler's theorem

In 1736, Leonhard Euler published a proof of Fermat's little theorem^[1] (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where n is a prime number. Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where n is not prime.^[2]


The converse of Euler's theorem is also true: if the above congruence is true, then ${\displaystyle a}$ and ${\displaystyle n}$ must be coprime.


The theorem is further generalized by some of Carmichael's theorems.


The theorem may be used to easily reduce large powers modulo ${\displaystyle n}$. For example, consider finding the ones place decimal digit of ${\displaystyle 7^{222}}$, i.e. ${\displaystyle 7^{222}{\pmod {10}}}$. The integers 7 and 10 are coprime, and ${\displaystyle \varphi (10)=4}$. So Euler's theorem yields ${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$, and we get ${\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}}$.


In general, when reducing a power of ${\displaystyle a}$ modulo ${\displaystyle n}$ (where ${\displaystyle a}$ and ${\displaystyle n}$ are coprime), one needs to work modulo ${\displaystyle \varphi (n)}$ in the exponent of ${\displaystyle a}$:


Euler's theorem underlies the RSA cryptosystem, which is widely used in Internet communications. In this cryptosystem, Euler's theorem is used with n being a product of two large prime numbers, and the security of the system is based on the difficulty of factoring such an integer.