Explore Euler’s Theorem and Fermat’s Theorem in our comprehensive article. Discover the fundamental principles in number theory, including modular exponentiation, totient function, and the relationships between coprime numbers and congruence. Gain insights into the applications of these theorems in cryptography and their significance in mathematical proofs. Enhance your understanding of these essential theorems with clear explanations and examples.
Table of Contents
Euler’s Theorem
Euler’s Theorem is defined as a function a^φ(n) ≡ 1 (mod n) where n is [n > or = 1] the number of integers less than n that are co-prime to n.
Euler’s Theorem establishes a relationship between the values of Euler’s Totient function and modular exponentiation.
Key points about Euler’s theorem
- Coprime Requirement: The theorem applies specifically to the case where ‘a’ and ‘n’ are coprime, meaning their greatest common divisor (GCD) is 1. This condition ensures the existence of an inverse modulo ‘n’ for ‘a’.
- Modular Exponentiation: The theorem relates the exponentiation of ‘a’ with the totient function of ‘n’, with the resulting value being congruent to 1 modulo ‘n’. This means that the remainder of dividing a^φ(n) by ‘n’ is 1.
- Euler’s Totient Function: The totient function φ(n) can be computed based on the prime factorization of ‘n’. For example, if ‘n’ is a prime number, then φ(n) = n – 1.
Let’s take an example –
n = 5
Explanation: Since the number of integers < n, therefore we take the integer values till 4.
Now find the Greatest Common Divisor of each integer with n i.e., 5. Make a pair of each integer with 5.
(5,1)
5 – 1,5
1 – 1
(5,2)
5 – 1,5
2 – 1,2
(5,3)
5 – 1,5
3 – 1,3
(5,4)
5 – 1,5
4 – 1,2,4
In the above all pairs of integers, only 1 is the GCD i.e., the number that is common to divide the set of numbers.
So, there is a total 4 number of integers which returns GCD 1 with 5.
φ(5) = [1,2,3,4] = 4 integers. [Integers are defined as the number/counting of total digits to ‘n’ that have GCD = 1.]
Hence, the theorem is proved since 4 integers are less than ‘n’ i.e., 5, and all integers are co-prime to ‘n’.
Let’s take an example –
n = 3
Explanation: Since the number of integers < n, therefore we take the integer values till 2.
Now find the Greatest common divisor of each integer with n i.e., 3. Make a pair of each integer with 3.
(3,1)
3 – 1, 3
1 – 1
(3,2)
3 – 1
2 – 1, 2
In the above all pairs of integers, only 1 is the GCD i.e., the number that is common to divide the set of numbers.
So, there is a total 2 number of integers that returns GCD 1 with 3.
φ(3) = [1,2] = 2 integers.
Hence, the theorem is proved since 2 integers are less than ‘n’ i.e., 3, and all integers are co-prime to ‘n’.
Formula:
In the function φ(n), If n is the prime number, then can be written as:
φ(n) = n-1
E.g., n = 17
φ(n) = 17-1
φ(17) = 17-1
φ(17) = 16
Explanation: If n is the Prime number, then we don’t need to follow all procedures of finding GCD, instead we can easily find the value by decrementing 1 from n.
So, there is a total 16 number of integers that returns GCD 1 with 17.
φ(17) = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] = 16 integers.
Hence, the theorem is proved since 16 integers are less than ‘n’ i.e., 17, and all integers are co-prime to ‘n’.
Formula:
Let’s say we have a number n = 35, if we can write the multiplication of n into two prime numbers in the form of a and b then the formula can be
φ(a*b) = φ(a) * φ(b)
where a and b are co-prime numbers, meaning both numbers GCD must be 1.
If we have a number that can be represented in the multiplication form of a and b; where a and b are prime numbers, then we can use the formula.
Note: n should be a bigger number.
E.g., n = 35
φ(a*b) = φ(a) * φ(b)
φ(35) = φ(7) * φ(5) [GCD (7,5) = 1]
= φ(6) * φ(4) [Note: φ(n) = n-1]
= 24
This means 24 integers are co-prime to n i.e., 35.
Let’s take another example –
E.g., n = 25
φ(a*b) = φ(a) * φ(b)
φ(25) = φ(5) * φ(5)
= φ(4) * φ(4) [Note: φ(n) = n-1]
= 16
This means 16 integers are co-prime to n i.e., 25.
Formula:
The formula a^φ(n) ≡ 1 (mod n) can be applied as φ(a*b) = φ(a) * φ(b), if the GCD of a and n is 1.
E.g., a = 4, n = 165 [GCD (4,165) = 1]
φ(a*b) = φ(a) * φ(b)
φ(165) = φ(15) * φ(11)
= φ(3) * φ(5) * φ(11) [since 15 is not a prime number, it is divided into two prime numbers, 3 and 5.]
= φ(2) * φ(4) * φ(10) [Note: φ(n) = n-1]
= 80
a^φ(n) ≡ 1 (mod n)
4^φ(80) ≡ 1 (mod 165)
When the 4 power will be raised to 80 times, will be divided by 165, then it will return 1 as the remainder.
Let’s take another example –
E.g., a = 5, n = 6 [GCD (5,6) = 1]
φ(a*b) = φ(a) * φ(b)
φ(6) = φ(2) * φ(3)
= φ(1) * φ(2) [Note: φ(n) = n-1]
= 2
a^φ(n) ≡ 1 (mod n)
5^φ(2) ≡ 1 (mod 6)
When the 5 power will be raised to 2 times, will be divided by 6, then it will return 1 as the remainder.
Fermat’s Theorem
Formula:
a power to (n-1) ≡ 1 (mod n)
Where n is the Prime number and a should not be divisible by n.
A not equal 0 (mod n)
Apply Euler’s Theorem to Fermat’s Theorem
φ(n) = n-1
Where n is the prime number.
According to above Euler’s Theorem,
This formula a^φ(n) ≡ 1 (mod n) will become:
a power to (n-1) ≡ 1 (mod n)
Remember that n must be a Prime number.
E.g., a = 5, n = 3
a^φ(n) ≡ 1 (mod n)
5 power to (3-1) ≡ 1 (mod 3)
5 power 2 ≡ 1 (mod 3)
25 ≡ 1 mod 3
Meaning that if we divide the 25 by 3 it gives 1 as the remainder. So, Fermat’s Theorem is correct with Euler’s Theorem.
E.g., a = 4, n = 5
a^φ(n) ≡ 1 (mod n)
4 power to (5-1) ≡ 1 (mod 5)
4 power 4 ≡ 1 (mod 5)
256 ≡ 1 mod 5
Meaning that if we divide the 256 by 5 it gives 1 as the remainder. So, Fermat’s Theorem is correct with Euler’s Theorem.
Conclusion
The article provides a comprehensive exploration of these fundamental principles in number theory. It highlights the key concepts and significance of both theorems, offering valuable insights into their mathematical foundations.
It explains Euler’s Theorem, which establishes a relationship between modular exponentiation and Euler’s totient function.
Furthermore, explores Fermat’s Theorem, which states that if ‘n’ is a prime number and ‘a’ is an integer coprime to ‘n’, then a^(n-1) ≡ 1 (mod n).
Overall, the article provides a comprehensive understanding of Euler’s Theorem and Fermat’s Theorem with practical examples.
