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

where ${\displaystyle \varphi (n)}$ is Euler's totient function. (The notation is explained in the article modular arithmetic.) In 1736, Leonhard Euler published his proof of Fermat's little theorem, which Fermat had presented without proof. Subsequently, Euler presented other proofs of the theorem, culminating with "Euler's theorem" in his paper of 1763, in which he attempted to find the smallest exponent for which Fermat's little theorem was always true.

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

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem.

The theorem may be used to easily reduce large powers modulo n. For example, consider finding the ones place decimal digit of 7²²², i.e. 7²²² (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 7⁴ ≡ 1 (mod 10), and we get 7²²²≡ 7^{4 × 55 + 2} ≡ (7⁴)⁵⁵ × 7² ≡ 1⁵⁵ × 7² ≡ 49 ≡ 9 (mod 10).

Note that if ${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$, then also ${\displaystyle (a^{\varphi (n)})^{k}\equiv 1{\pmod {n}}}$ for any positive k, because of

...
Wikipedia