What is Fermat’s Little Theorem?
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 Theorem
1. What is the precise statement of Fermat's Little Theorem?
Fermat's Little Theorem states that if p is a prime number, then for any integer a that is not divisible by p, the number ap-1 - 1 will be an integer multiple of p. In modular arithmetic notation, this is expressed as:
- ap-1 ≡ 1 (mod p)
A more general form, which works for any integer a (even if divisible by p), is stated as ap ≡ a (mod p).
2. How can you use Fermat's Little Theorem to find the remainder of a large power?
Fermat's Little Theorem is highly effective for simplifying large power calculations and finding remainders when dividing by a prime number. For example, to find the remainder of 3100 when divided by 13 (a prime number), you can apply the theorem. Here, a = 3 and p = 13. According to the theorem, 313-1 ≡ 312 ≡ 1 (mod 13). You can then rewrite 100 as (12 × 8) + 4. So, 3100 becomes (312)8 × 34. Since 312 is congruent to 1, this simplifies to 18 × 34 ≡ 81 (mod 13). The remainder of 81 divided by 13 is 3, so 3100 ≡ 3 (mod 13).
3. What is the main application of Fermat's Little Theorem?
The primary application of Fermat's Little Theorem is in primality testing. The theorem provides a way to test if a number is likely prime. If we want to check if a number 'n' is prime, we can pick an integer 'a' not divisible by 'n' and calculate an-1 (mod n). If the result is not 1, then 'n' is definitely not a prime number. If the result is 1, 'n' is likely a prime number (though some composite numbers, called Carmichael numbers, can also pass this test).
4. What is the difference between Fermat's Little Theorem and Fermat's Last Theorem?
These are two completely different theorems.
- Fermat's Little Theorem is a fundamental result in number theory concerning modular arithmetic. It states that for a prime number 'p' and an integer 'a' not divisible by 'p', ap-1 has a remainder of 1 when divided by p.
- Fermat's Last Theorem is a famous statement about Diophantine equations. It asserts that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than 2. This theorem remained unproven for over 350 years until Andrew Wiles published a proof in 1995.
5. How is Fermat's Little Theorem applied in modern cryptography?
Fermat's Little Theorem is a foundational concept behind public-key cryptography, particularly the RSA algorithm. The security of RSA relies on the difficulty of factoring large numbers. The theorem (and its generalisation, Euler's totient theorem) is used in the key generation and the encryption/decryption processes. It ensures that the mathematical operations of encrypting with a public key and decrypting with a private key are inverses of each other, allowing the original message to be recovered.
6. Is Fermat's Theorem related to finding the maximum and minimum in calculus?
No, that is a different theorem also formulated by Pierre de Fermat. The theorem used in calculus is Fermat's Theorem on Stationary Points. It states that if a function has a local maximum or minimum at a point 'c', and if the derivative f'(c) exists, then f'(c) must be zero. This is a critical concept for finding optimisation points in calculus and is unrelated to the number theory concepts of Fermat's Little Theorem.
7. What is the significance of Fermat's Little Theorem in group theory?
In the context of abstract algebra, Fermat's Little Theorem is a direct consequence of Lagrange's Theorem. The set of integers from 1 to p-1 forms a group of order p-1 under multiplication modulo p, denoted as (Z/pZ)×. According to Lagrange's Theorem, the order of any element 'a' in this group must divide the order of the group itself. Therefore, ap-1 must be congruent to the identity element, which is 1 (mod p). This connection showcases a deep link between elementary number theory and the more abstract structure of groups.
