Euler's theorem

In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if n and a are <a href="/facts/Coprime/bnCxCXxs">coprime</a> positive integers, then 
 
 
 
 
 a
 
 φ
 (
 n
 )
 
 
 
 
 {\displaystyle a^{\varphi (n)}}
 
 is congruent to 
 
 
 
 1
 
 
 {\displaystyle 1}
 
 <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> n, where 
 
 
 
 φ
 
 
 {\displaystyle \varphi }
 
 denotes <a href="/facts/Euler%2527s_totient_function/mIQwXYzj">Euler's totient function</a>; that is

a
          
            φ
            (
            n
            )
          
        
        ≡
        1
        
          
          (
          mod
          
          n
          )
        
        .
      
    
    {\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}.}

In 1736, <a href="/facts/Leonhard_Euler/z2fsbjgj">Leonhard Euler</a> published a proof of <a href="/facts/Fermat%2527s_little_theorem/qIjSIm2s">Fermat's little theorem</a> (stated by <a href="/facts/Pierre_de_Fermat/FLbUh75u">Fermat</a> 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
 
 
 {\displaystyle a}
 
 and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 must be coprime.
The theorem is further generalized by some of <a href="/facts/Carmichael_function/D0l0I6od">Carmichael's theorems</a>.
The theorem may be used to easily reduce large powers modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
. For example, consider finding the ones place decimal digit of 
 
 
 
 
 7
 
 222
 
 
 
 
 {\displaystyle 7^{222}}
 
, i.e. 
 
 
 
 
 7
 
 222
 
 
 
 
 (
 mod
 
 10
 )
 
 
 
 {\displaystyle 7^{222}{\pmod {10}}}
 
. The integers 7 and 10 are coprime, and 
 
 
 
 φ
 (
 10
 )
 =
 4
 
 
 {\displaystyle \varphi (10)=4}
 
. So Euler's theorem yields 
 
 
 
 
 7
 
 4
 
 
 ≡
 1
 
 
 (
 mod
 
 10
 )
 
 
 
 {\displaystyle 7^{4}\equiv 1{\pmod {10}}}
 
, and we get 
 
 
 
 
 7
 
 222
 
 
 ≡
 
 7
 
 4
 ×
 55
 +
 2
 
 
 ≡
 (
 
 7
 
 4
 
 
 
 )
 
 55
 
 
 ×
 
 7
 
 2
 
 
 ≡
 
 1
 
 55
 
 
 ×
 
 7
 
 2
 
 
 ≡
 49
 ≡
 9
 
 
 (
 mod
 
 10
 )
 
 
 
 {\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 
 
 
 
 a
 
 
 {\displaystyle a}
 
 modulo 
 
 
 
 n
 
 
 {\displaystyle n}
 
 (where 
 
 
 
 a
 
 
 {\displaystyle a}
 
 and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 are coprime), one needs to work modulo 
 
 
 
 φ
 (
 n
 )
 
 
 {\displaystyle \varphi (n)}
 
 in the exponent of 
 
 
 
 a
 
 
 {\displaystyle a}
 
:

if 
 
 
 
 x
 ≡
 y
 
 
 (
 mod
 
 φ
 (
 n
 )
 )
 
 
 
 {\displaystyle x\equiv y{\pmod {\varphi (n)}}}
 
, then 
 
 
 
 
 a
 
 x
 
 
 ≡
 
 a
 
 y
 
 
 
 
 (
 mod
 
 n
 )
 
 
 
 {\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}
 
.
Euler's theorem underlies the <a href="/facts/RSA_(cryptosystem)/XTzyfHuq">RSA cryptosystem</a>, which is widely used in <a href="/facts/Internet/Xw1rVvJU">Internet</a> communications. In this cryptosystem, Euler's theorem is used with n being a product of two large <a href="/facts/Prime_number/L20FLkgn">prime numbers</a>, and the security of the system is based on the difficulty of <a href="/facts/Integer_factorization/EjMCTz2t">factoring</a> such an integer.

Euler's theorem open-in-new

Euler's theorem