Fermat’s Little Theorem states that for a prime number p , the following statement holds true –
ap ≡ a (mod p) (~ which can be read as ap mod p = a)
ap-1 ≡ 1 (mod p)
Here a is any number less than p.
There are tons of proofs for Fermat’s Little Theorem on Wikipedia . I am discussing an easy one based on binomial expansion – Proof by Induction.
Consider a binomial expression – (1+a)p
On expanding it , we get –
(1+a)p = ap + pC1 ap-1 + pC2 ap-2 + pC3 ap-3 …… + 1
If we take modulo p both sides, All the terms except the first and the last term becomes 0.
How? Let’s See.
Consider a binomial coefficient – pCk = p! ⁄ (p-k)! (k)!
Since p is prime (no divisors) ,pCk will have p as it’s divisor .Thus modulo p will yield 0 as result.
we get –
(1+a)p ≡ ap + 1 mod p
Considering the Fermat’s Little theorem true , we can replace ap mod p by a
We get the following result – (1+a)p ≡ (1+a) mod p
Thus Fermat’s Little Theorem is proved by Induction.
Now that we’ve proved the theorem , let’s see how we can use it to check the probabilistic primality of a number.
To check whether a number p is prime or not, just take a random a less than p and verify the theorem.
if (ap-1 mod p) yields 1 as result , then the number may be prime.
To increase the accuracy of the algorithm,perform the check for a certain number of iterations.
Here’s the python Code for the Algorithm
if (p==2 or p==3):return 1
if (p<=3):return 0
#number of iterations = 10
for i in range(10):
#Generating a random number a lesser than p
a = random.randrange(2,p-1)
The time complexity of the Algorithm is O(iterations*log(n)) which is pretty fast. But the algorithm is not always accurate as there may be many composite numbers p which may yield the result for some value of a. Therefore it is advised to perform the check for certain number of iterations.
Also there are certain composite numbers n which satisfies the Fermat’s Little congruence relation for all values 1<a<n (a is relatively prime to n). Such numbers are called Carmichael numbers.
But they are very less in number – around 2000 under 25,000,0000,000.
Here’s a problem to try – SPOJ/PON
The Fermat’s result proved above ap-1 ≡ 1 (mod p) can be rewritten as a.ap-2 ≡ 1 (mod p).
In the expression a.x ≡ 1 (mod p) , x is the inverse of a.
Thus, when p is prime , (1⁄a) mod p , is given by ap-2 mod p .
For any queries related to the article , feel free to drop a comment below 🙂
EDIT – If you’re trying to implement the above algorithm on C/C++, take care of overflows while multiplying two long long int numbers.