Euler's theorem

In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are coprime positive integers, then ${\displaystyle a^{\varphi (n)}}$ is congruent to ${\displaystyle 1}$ modulo n, where ${\displaystyle \varphi }$ denotes Euler's totient function; that is

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}.}$

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}$:

if ${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$, then ${\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}$.

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.