Fermat’s Little Theorem states that for a **prime** number **p** , the following statement holds true –

a^{p} ≡ a (mod p) (~ which can be read as a^{p} mod p = a)

**OR**

a^{p-1} ≡ 1 (mod p)

Here **a **is any number less than **p.**

## PROOF

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} = a^{p} + ^{p}C_{1} a^{p-1} + ^{p}C_{2} a^{p-2} + ^{p}C_{3} a^{p-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 – ^{p}C_{k } = ^{p!} ⁄ _{(p-k)! (k)!}

Since **p **is prime (no divisors) ,^{p}C_{k } will have p as it’s divisor .Thus modulo p will yield **0** as result.

we get –

**(1+a)**^{p} ≡ a^{p} + 1 mod p

Considering the Fermat’s Little theorem true , we can replace **a**^{p} 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.

## PRIME Algorithm

To check whether a number **p **is prime or not, just take a random **a** less than p and verify the theorem.

if (**a**^{p-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

import random
def exp(a,p,m):
if (p==0):
return 1
elif (p%2==1):
return (a*exp(a,p-1,m))%m
x=exp(a,p/2,m)
return (x*x)%m
def fermat_primality(p):
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)
if (exp(a,p-1,p)!=1):
return 0
return 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

## INVERSE MODULO

The Fermat’s result proved above **a**^{p-1} ≡ 1 (mod p) can be rewritten as **a**.**a**^{p-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 **a**^{p-2} mod p .

def exp(a,p,m):
if (p==0):
return 1
elif (p%2==1):
return (a*exp(a,p-1,m))%m
x=exp(a,p/2,m)
return (x*x)%m
def mod_inverse(a,p):
return exp(a,p-2,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.

### Like this:

Like Loading...