Table of Contents

Last modified on April 26th, 2024

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.

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.

Let us consider the elements r_{1}, r_{2}, …, 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_{1}, ar_{2}, …, ar_{φ(n)}} equals (ℤ/n)×

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

r_{1}r_{2}…r_{φ(n)} ≡ (ar_{1})(ar_{2})…(ar_{φ(n)})

⇒ r_{1}r_{2}…r_{φ(n)} ≡ a^{φ(n)} r_{1}r_{2}…r_{φ(n)}

⇒ 1 ≡ a^{φ(n)}

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

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^{2}, …, 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.

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.

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.

**Use Euler’s remainder theorem to find the remainder when 2 ^{70} is divided by 15.**

Solution:

As we know, Euler’s remainder theorem is a^{φ(n)} ≡ 1 (mod n)

Here,

n = 15 and a = 2 are two coprime numbers

n = x^{p }y^{q }z^{r} = 15 = 3 × 5

By calculating the Euler’s function, we get

φ(n)

= ${n\left( 1-\dfrac{1}{x}\right) \left( 1-\dfrac{1}{y}\right) \left( 1-\dfrac{1}{z}\right)}$

= ${15\left( 1-\dfrac{1}{3}\right) \left( 1-\dfrac{1}{5}\right)}$

= 8

Now, 2^{8} = 256

On diving 2^{70} by 15, we get

2^{70} ≡ (2^{8})^{8} ⋅ 2^{6} ≡ 1^{8} ⋅ 64 ≡ 64 ≡ 4 (mod 15)

Thus, when 2^{70} is divided by 15, the remainder is 4.

**What is the remainder of 7 ^{129 }on division with 33?**

Solution:

By Fermat’s theorem, we get 7^{33 – 1} = 7^{32} ≡ 1 (mod 33), where 7 and 33 are coprime numbers.

Here, 7^{129} = (7^{32})^{4} ⋅ 7 ≡ 1 ⋅ 7 ≡ 7 (mod 33)

Thus, the remainder of 7^{129} upon division by 33 is 7

**Show that n divides 2 ^{(n – 1)!} – 1, for any odd integer n.**

Solution:

For n = 1, the given statement becomes 2^{(1-1)!} – 1 = 2^{1} – 1 = 2, which is divisible by 1

Let us assume for n > 1

By Euler’s theorem, we get 2^{φ(n)} ≡ 1 (mod n)

Since φ(n) ≤ (n – 1), φ(n) divides (n – 1)!

(n – 1)! = φ(n) ⋅ k for some integer k

2^{(n – 1)!} ≡ 2^{φ(n) ⋅ k} ≡ (2^{φ(n)})^{k} ≡ 1^{k} ≡ 1 (mod n)

Thus, 2^{(n – 1)!} – 1 is divisible by any odd integer n.

Last modified on April 26th, 2024