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

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 pThus 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

*prime.*

**may be**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 pdef 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.