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, and {displaystyle varphi (n)} is Euler's totient function, then a raised to the power {displaystyle varphi (n)} is congruent to 1 modulo n; 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 Carmichael's theorem.

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^{4times 55+2}equiv (7^{4})^{55}times 7^{2}equiv 1^{55}times 7^{2}equiv 49equiv 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 xequiv 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.