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
a
φ
(
n
)
{\displaystyle a^{\varphi (n)}}
is congruent to
1
{\displaystyle 1}
modulo n, where
φ
{\displaystyle \varphi }
denotes Euler's totient function; that is
a
φ
(
n
)
≡
1
(
mod
n
)
.
{\displaystyle 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
{\displaystyle a}
and
n
{\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
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 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
φ
(
n
)
=
a
k
M
=
(
a
k
)
M
≡
1
M
=
1
(
mod
n
)
.
{\displaystyle a^{\varphi (n)}=a^{kM}=(a^{k})^{M}\equiv 1^{M}=1{\pmod {n}}.}