# 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 = xp yq zr, 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 r1, r2, …, 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 {ar1, ar2, …, arφ(n)} equals  (ℤ/n)×

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

r1r2…rφ(n) ≡ (ar1)(ar2)…(arφ(n)

⇒ r1r2…rφ(n) ≡ aφ(n) r1r2…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, a2, …, ad – 1), where ‘d’ is the multiplicative order of ‘a’

By Lagrange’s theorem,

d|φ(n)

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

Since ad ≡ 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 ab ≡ a (mod n)

Proof

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

Here, ab ≡ ak ⋅ φ(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, ab ≡ 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) ≡ an – 1 ≡ 1 (mod n)

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

## Solved Examples

Use Euler’s remainder theorem to find the remainder when 270 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 = xp yq zr = 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, 28 = 256
On diving 270 by 15, we get
270 ≡ (28)8 ⋅ 26 ≡ 18 ⋅ 64 ≡ 64 ≡ 4 (mod 15)
Thus, when 270 is divided by 15, the remainder is 4.

What is the remainder of 7129 on division with 33?

Solution:

By Fermat’s theorem, we get 733 – 1 = 732 ≡ 1 (mod 33), where 7 and 33 are coprime numbers.
Here, 7129 = (732)4 ⋅ 7 ≡ 1 ⋅ 7 ≡ 7 (mod 33)
Thus, the remainder of 7129 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 = 21 – 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 ≡ 1k ≡ 1 (mod n)
Thus, 2(n – 1)! – 1 is divisible by any odd integer n.