Fermats 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.