Euler's theorem

This article page is a stub, please help by expanding it.

Euler’s theorem pertains to congruences and powers. The theorem was formulated and proved by Leonhard Euler in 1736.

Theorem. (Euler)

Given an integer

n   ≥   2

and a positive integer

b

coprime to

n

, the congruence

b φ (n)   ≡   1  (mod n)

, where

φ (n)

is Euler’s totient function, holds.

Proof. Consider the

φ (n)

numbers

b, a2 b, a3 b, ..., aφ (n) b,

where

1, a2, a3, ..., aφ (n)

are the integers coprime to

n

(i.e. the totatives of

n

). Those are all different and nonzero

(mod n)

, since

b

is coprime to

n

. Indeed, if

u b   ≡   v b  (mod n)

, then

u   ≡   v  (mod n)

, since we can “cancel the

b

” (

b

being coprime to

n

). So we have

φ (n)

numbers, all different, and none of them is

0  (mod n)

. So they must be congruent to

1, a2, a3, ..., aφ (n)

in some order. Multiplying them together, we get

P = Πφ(n) b φ (n)

, where

Πφ(n)

is the coprimorial of

n

. So their product is congruent to

Πφ(n)  (mod n)

. We now have two expressions for this product, so we can equate them:

Πφ(n) b φ (n)   ≡   Πφ(n)  (mod n)

. Now

Πφ(n)

is coprime to

n

, so we can again cancel, to give

b φ (n)   ≡   1  (mod n)

. □

Fermat’s little theorem is a special case of Euler’s theorem so that

b  p  − 1   ≡   1  (mod p)

if

gcd (b, p) = 1

, since for a prime

p

we have

φ (  p) = p  −  1

and

gcd (b, p) = 1

for any

b

not a multiple of

p

. Note also that for Carmichael numbers, for which

φ (n) ∣ n  −  1

, we have

b  n  − 1   ≡   1  (mod n)

if

gcd (b, n) = 1

.

See also

• Fermat’s little theorem
• Euler’s totient function