What is Euler's theorem?

Euler's theorem

Euler's theorem is a generalization of Fermat's little theorem. Euler's theorem extends Fermat's little theorem by removing the imposed condition where $n$ must be a prime number. This allows Euler's theorem to be used on a wide range of positive integers. It states that if a random positive integer $a$ and $n$ are co-primeTwo numbers are considered to be co-prime if the only positive integer that divides them is 1, meaning that greatest common divisor of a and n is 1. GCD(a, n) = 1, then $a$ raised to the power Euler's totient function $\varphi(n)$ is congruent to $1 \, (mod\, n)$. The mathematical form is as follows:

However, if $n$ is a prime number, Euler's theorem is simplified to Fermat's little theorem as follows:

As $\varphi(n) = n - 1$, where $n$ is a prime number, we can plug the value of the totient function into the equation above resulting in the equation as follows:

This becomes the alternate form of Fermat's little theorem.

Examples

The examples of Euler's theorem with varying values of $a$ and $n$ are given below.

Example 1

Let $a = 4$ and $n = 7$, $a$ and $n$ are co-prime as their greatest common divisor is $1$. Now plug the values into Euler's equation above resulting in the equation as follows:

As $\varphi(7) = 6$, we plug this value into the equation above resulting in the equation as follows:

We then simplify it as follows:

This equation suggests if we divide $4096$ by $7$, we will get a reminder of $1$. This proves that Euler's theorem is valid on the given values.

Example 2

Euler's theorem can be used to simplify and solve more complex problems where the values of $a$ and $n$ are not properly defined. Instead, a complex problem is given as follows:

The numbers $3$ and $10$are co-prime, so we can apply Euler's theorem to this problem. Considering the equation above, we can take the values of $a$ and $n$ to be $3$ and $10$, respectively. Applying these values to Euler's theorem, the equation is as follows:

As $\varphi(10) = 4$, we plug this value into the equation above resulting in the equation as follows:

Using the equation above, we know that if we divide $3^4$ by $10$, the remainder will be $1$, but the original problem contains $3^{44}$. So we simplify the original problem as follows:

We can replace $3^4$ with $1$, as $3^{4} \,\cong 1\, (mod \,10)$

Euler's theorem allows us to convert complex problems into simpler, computationally less expensive problems.

Application of Euler's theorem

Euler's theorem and Euler's totient function serve as a base for the modern RSA encryption algorithm. Euler's theorem is involved in the following processes of the RSA algorithm.

• Key generation process
• Encryption
• Decryption