# Euler's theorem

(Redirected from Euler 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, and $\varphi (n)$ is Euler's totient function, then a raised to the power $\varphi (n)$ is congruent to 1 modulo n; that is

$a^{\varphi (n)}\equiv 1{\pmod {n}}.$ In 1736, Leonhard Euler published a proof of Fermat's little theorem (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.

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 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^{222}$ , i.e. $7^{222}{\pmod {10}}$ . The integers 7 and 10 are coprime, and $\varphi (10)=4$ . So Euler's theorem yields $7^{4}\equiv 1{\pmod {10}}$ , and we get $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 $a$ modulo $n$ (where $a$ and $n$ are coprime), one needs to work modulo $\varphi (n)$ in the exponent of $a$ :

if $x\equiv y{\pmod {\varphi (n)}}$ , then $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.

## Proofs

1. Euler's theorem can be proven using concepts from the theory of groups: The residue classes modulo n that are coprime to n form a group under multiplication (see the article Multiplicative group of integers modulo n for details). The order of that group is φ(n). Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case φ(n). If a is any number coprime to n then a is in one of these residue classes, and its powers a, a2, ... , ak modulo n form a subgroup of the group of residue classes, with ak ≡ 1 (mod n). Lagrange's theorem says k must divide φ(n), i.e. there is an integer M such that kM = φ(n). This then implies,

$a^{\varphi (n)}=a^{kM}=(a^{k})^{M}\equiv 1^{M}=1{\pmod {n}}.$ 2. There is also a direct proof: Let R = {x1, x2, ... , xφ(n)} be a reduced residue system (mod n) and let a be any integer coprime to n. The proof hinges on the fundamental fact that multiplication by a permutes the xi: in other words if axjaxk (mod n) then j = k. (This law of cancellation is proved in the article Multiplicative group of integers modulo n.) That is, the sets R and aR = {ax1, ax2, ... , axφ(n)}, considered as sets of congruence classes (mod n), are identical (as sets—they may be listed in different orders), so the product of all the numbers in R is congruent (mod n) to the product of all the numbers in aR:

$\prod _{i=1}^{\varphi (n)}x_{i}\equiv \prod _{i=1}^{\varphi (n)}ax_{i}=a^{\varphi (n)}\prod _{i=1}^{\varphi (n)}x_{i}{\pmod {n}},$ and using the cancellation law to cancel each xi gives Euler's theorem:
$a^{\varphi (n)}\equiv 1{\pmod {n}}.$ 