Euler’s Theorem

Euler’s theorem or Euler’s totient theorem is an expansion of Fermat’s little theorem, which states that:

If an integer ‘a’ is relatively prime to any positive integer ‘n,’ and φ(n) is the number of positive integers (≤ n) that are relatively prime to ‘n,’ then

a^φ(n) ≡ 1 (mod n)

Here,

n = x^p y^q z^r, for any natural number ‘n’

φ(n) = ${n\left( 1-\dfrac{1}{x}\right) \left( 1-\dfrac{1}{y}\right) \left( 1-\dfrac{1}{z}\right)}$, is known as Euler’s totient function or Euler’s function.

It has many applications in elementary number theory, including the theoretical basis for RSA cryptography, where a wide range of positive integers are used.

Proof

To prove Euler’s Theorem, we rely on several fundamental concepts from number theory, including the properties of Euler’s totient function and the concept of modular arithmetic. Here’s a simplified version of the proofs.

Using Residue Classes

Let us consider the elements r₁, r₂, …, r_φ(n) of (ℤ/n)×, the congruence classes of integers that are relatively prime to ‘n.’

Since multiplication by ‘a’ is a function from the finite set (ℤ/n)× to itself and has an inverse for a Є (ℤ/n)×, then {ar₁, ar₂, …, ar_φ(n)} equals  (ℤ/n)×

Now, considering the product of all the elements of (ℤ/n)× in modulo n, we get

r₁r₂…r_φ(n) ≡ (ar₁)(ar₂)…(ar_φ(n)) 

⇒ r₁r₂…r_φ(n) ≡ a^φ(n) r₁r₂…r_φ(n)

⇒ 1 ≡ a^φ(n)

⇒ a^φ(n) ≡ 1 (mod n), and thus, the theorem is proven.

Using Lagrange’s Theorem

The elements in (ℤ/n) with multiplicative inverses form a group under the multiplication, denoted by (ℤ/n)×, which has φ(n) elements.

Let us assume that the subgroup consisting of the powers of ‘a’ has ‘d’ elements

The elements of the subgroup are {1, a, a², …, a^{d – 1}), where ‘d’ is the multiplicative order of ‘a’

By Lagrange’s theorem,

d|φ(n)

⇒ φ(n) = dk, for some integer k

Since a^d ≡ 1 (mod n)

a^φ(n) ≡ a^dk ≡ (a^d)^k ≡ 1^k ≡ 1 (mod n)

Hence, Euler’s theorem is proven.

Corollary

From Euler’s theorem, we get several corollaries. Some are discussed below.

Corollary 1: If n Є ℤ⁺, a Є ℤ, and ‘a’ coprime to ‘n,’ then a^{φ(n) + 1} ≡ a (mod n)

Proof

Here, a^{φ(n) + 1} ≡ a^φ(n) ⋅ a (mod n)

Since, according to Euler’s theorem, a^φ(n) ≡ 1 (mod n), then

a^φ(n) ⋅ a ≡ 1 ⋅ a ≡ a (mod n)

Thus, a^{φ(n) + 1} ≡ a (mod n) is proven.

Corollary 2: If n Є ℤ⁺, a Є ℤ, ‘a’ coprime to ‘n,’ and b ≡  1 (mod n), then a^b ≡ a (mod n)

Proof

If b = 1 (mod φ(n)), then b = k ⋅ φ(n) + 1 for some integer k.

Here, a^b ≡ a^{k ⋅ φ(n) + 1} ≡ (a^φ(n))^k ⋅ a

Since, according to Euler’s theorem, a^φ(n) ≡ 1 (mod n), then

(a^φ(n))^k ≡ (1)^k ≡ 1 (mod n)

⇒ (a^φ(n))^k ⋅ a ≡ 1 ⋅ a ≡ a (mod n)

Thus, a^b ≡ a (mod n) is proven.

Generalization of Fermat’s Little Theorem

Euler’s theorem can be simplified to Fermat’s little theorem.

If n is a prime number, φ(n) = n – 1

Then, the theorem becomes a^φ(n) ≡ a^{n – 1} ≡ 1 (mod n) 

⇒ a^{n – 1} ≡ 1 (mod n), which is the alternate form of Fermat’s little theorem.

Solved Examples