What is Fermats Little Theorem Definition Formula Proof and Solved Examples
Fermat's little theorem is said to be the basis for the Fermat primality test and is one of the fundamental results of elementary number theory. The theorem is named after Pierre de Fermat, who stated it in the year 1640. To distinguish it from Fermat's last theorem, It is known as the "little theorem".
On this page, we are going to discuss Fermat’s little theorem example as well as Fermat’s little theorem exercises.
History of Fermat’s Last Theorem
The proof of Fermat's Last Theorem marks the end of a mathematical era and since virtually all of the tools which were eventually brought to bear on the problem had yet to be invented in the time of Fermat, it is quite interesting to speculate about whether he actually was in possession of an elementary proof of the theorem. According to the relentlessness with which the issue opposed assault for such a long time, Fermat's supposed verification appears prone to have been illusionary. This end is additionally upheld by the way that Fermat looked for pieces of evidence.
Fermat’s little theorem states that let’s say if p is a prime number, then for any integer suppose a, the number a p – a is an integer multiple of p.
Here p is a prime number
a\[^{p}\] ≡ a (mod p).
Special Case of Fermat’s Little Theorem: If a is not divisible by p, Fermat’s little theorem is equivalent to the statement that a\[^{p-1}\] -1 is an integer multiple of p.
a\[^{p-1}\] -1 ≡ 1 (mod p)
OR
a\[^{p-1}\] % p = 1
Here a is not divisible by p.
Fermat’s Little Theorem Example
Example:
P = an integer Prime number, a = an integer which is not multiple of P
Let a = 2 and P = 17
According to Fermat's little theorem
2 17 - 1 ≡ 1 mod(17), we got 65536 % 17 ≡ 1 that mean (65536-1) is an multiple of 17
Proof of Fermat’s Little Theorem
Start by listing the first p-1 positive multiples of a that are: a, 2a, 3a, ... (p -1)a
Suppose that ra, as well as, sa are the same modules of p, then we have r = s (mod p), so the p-1 multiples of the above are distinct and nonzero; that is, they must be congruent to 1, 2, 3, ..., p-1 in some given order. Multiply all these congruences together and we find
a (2a) (3a) ... ((p-1)a) ≡ 1.2.3.....(p-1) (mod p) which is, ap-1(p-1)! ≡ (p-1)! (mod p).
Divide both sides by (p-1)! to complete the proof. Sometimes Fermat's Little Theorem can be presented in the following form:
Corollary - Let p be a prime and a be any integer, then a\[^{p}\] ≡ a (mod p).
Proof - The result is trivial (both sides are zero) if p divides a. If p does not divide a, then we need to only multiply the congruence in Fermat's Little Theorem by a to complete the Fermat’s Little Theorem proof.
Proof of Fermat’s Theorem Using Group Theory
Using group theory to prove Fermat’s little theorem, recognize that the set G equal {1, 2, …, p − 1} with the operation of multiplication generally forms a group. Of the four group axioms, the only one that requires effort to verify is the fourth axiom, namely that the elements in G are said to be invertible.
If we assume that every element in G is said to be invertible, assume that a is in the range 1 ≤ a ≤ p − 1, that is, assume a is an element of G. Let k be the order of a, i.e. the smallest positive integer such that aᵏ ≡ 1 (mod p) is true, that is it holds. Then the numbers 1, a, a², …, aᵏ⁻¹ reduced modulo p, these form a subgroup of G whose order is equal to k. Therefore, by Lagrange’s theorem, k divides the order of G, which is equal to p − 1. So p − 1 = km for some positive integer let’s say m, and:
a\[^{p-1}\] ≡ a\[^{km}\] ≡ (a\[^{k}\])\[^{m}\] ≡ 1\[^{m}\] ≡ 1(mod p)
Now, to prove that every element b of G coprime to p is invertible, this identity can help us as follows. Because b as well as p are coprime, Bézout’s identity assures that there are integers c as well as d such that bc + pd equals 1. Modulo p implies that c is an inverse for b and this is because bc ≡ 1 (mod p). Because b is said to be invertible, so is every other element in G, and so G must be a group.
Application of Fermat’s Little Theorem - Primality Test
Fermat’s little theorem is said to become the basis for the Fermat primality test, a probabilistic method of determining whether a number is a probable prime. If we for instance want to find out whether n equals 19 is prime, randomly pick 1 < a < 19, say a equals 2. Calculate n − 1 equals 18, and its factors: 9 and 6. We check by calculating 2¹⁸ ≡ 1 (mod 19), 2⁹ ≡ 18 (mod 19), and 2⁶ ≡ 7 (mod 19) and we must check that 19 must be prime.
FAQs on Fermats Little Theorem Explained with Proof and Applications
1. What is Fermat’s Last Theorem?
Fermat’s Last Theorem states that the equation xn + yn = zn has no positive integer solutions for any integer n > 2.
- It was proposed by Pierre de Fermat in 1637.
- It generalizes the Pythagorean equation (which works only for n = 2).
- The theorem remained unproven for over 350 years.
2. What is Fermat’s Little Theorem?
Fermat’s Little Theorem states that if p is a prime number and a is not divisible by p, then ap−1 ≡ 1 (mod p).
- It is widely used in modular arithmetic and number theory.
- It helps simplify large powers modulo a prime number.
- Equivalent form: ap ≡ a (mod p).
3. Who proved Fermat’s Last Theorem?
Fermat’s Last Theorem was proved by Sir Andrew Wiles in 1994.
- He used advanced concepts from algebraic geometry and modular forms.
- The proof relied on the Taniyama–Shimura–Weil conjecture.
- It is one of the most famous achievements in modern mathematics.
4. What is the formula for Fermat’s Little Theorem?
The main formula for Fermat’s Little Theorem is ap−1 ≡ 1 (mod p), where p is prime and gcd(a, p) = 1.
- Another common form is ap ≡ a (mod p).
- It applies only when p is prime.
- It simplifies modular exponentiation problems.
5. Can you give an example of Fermat’s Little Theorem?
Yes, for example, if p = 5 and a = 2, then 24 ≡ 1 (mod 5).
- Compute 24 = 16.
- Divide 16 by 5 → remainder is 1.
- So 16 ≡ 1 (mod 5).
6. Why doesn’t Fermat’s Last Theorem work for n = 2?
Fermat’s Last Theorem excludes n = 2 because the equation has solutions when n = 2, known as Pythagorean triples.
- Example: 3² + 4² = 5².
- Many integer solutions exist for n = 2.
- The theorem only applies for powers greater than 2.
7. What is the difference between Fermat’s Last Theorem and Fermat’s Little Theorem?
Fermat’s Last Theorem concerns integer solutions of powers, while Fermat’s Little Theorem deals with modular arithmetic and prime numbers.
- Last Theorem: No solutions for xn + yn = zn, n > 2.
- Little Theorem: ap−1 ≡ 1 (mod p) for prime p.
- Last Theorem is about Diophantine equations; Little Theorem is about congruences.
8. How is Fermat’s Little Theorem used in cryptography?
Fermat’s Little Theorem is used in cryptography to simplify modular exponentiation and compute modular inverses.
- It forms part of the theory behind RSA encryption.
- Helps compute a−1 mod p using ap−2 mod p.
- Ensures secure communication using prime numbers.
9. What are the conditions for applying Fermat’s Little Theorem?
The conditions for Fermat’s Little Theorem are that p must be prime and a must not be divisible by p.
- gcd(a, p) = 1.
- The modulus must be a prime number.
- If p is not prime, the theorem may not hold.
10. What is a common mistake when using Fermat’s Little Theorem?
A common mistake is applying Fermat’s Little Theorem when the modulus is not prime.
- The theorem works only for prime modulus p.
- Using it with composite numbers can give incorrect results.
- Another mistake is forgetting the condition gcd(a, p) = 1.
