Fermat's Little Theorem

Before I begin let us visit the topic of “numbers prime to each other.”

Recall that two numbers are called ‘prime to each other’ if they don’t have any prime factor in common.
Such numbers are also called co prime to each other.
It follows that if they don’t have any prime factor in common they don’t have any factor in common be it prime or composite.

How can we be sure that two numbers are co prime.

Say 1001 and 14.

How do we find out if they are co prime?
Factorise each of them into primes.

1001 =13*7*11

14=7*2

They have a 7 in common. So they cannot be co prime.

But
35 and 11

18 and 25

39 and 7

171 and 62

Are all co primes

If you think a bit you’ll realize that GCD of co prime numbers is 1.
In GCD what are we looking for are prime factors which are present in prime factorization of both the numbers. If they don’t have anything in common there GCD has to be 1.That is only 1 can divide both of them and leave no remainder.


Another good way to think of co prime numbers is this..

Say a and b are co prime
Then the fraction a/b cannot be reduced any further.
Why because we don’t have anything common in numerator and denominator that can be cancelled out.
Say 14/9 it cannot be reduced

But 14/49 can be reduced to 2/7

by cancelling out 7 in numerator and denominator

With that in mind we start with Fermat’s Little Theorem.

It says



a^(p-1) = 1 (mod p)

if ‘a is prime ‘

and ‘a and p are co prime’



What is nice about this theorem is RHS. It is 1

Often we are given sums like..
What is the remainder when 27^5977 is divided by 7.
We realize immediately that 7 is prime
And 27 is co prime with 7
We forget the giant number 5977 given to scare us and write the result we can get from Fermat’s theorem
The result is.

27^(7-1) =1 (mod 7 )
27^6 =1 (mod 7)

This result is then exploited to arrive at the sought remainder quickly.
We figure out how many times 5977 goes by 6.

5977= 996*6+1
Therefore
27^(5977)=27^(996*6+1) = (27^(996*6) ) * ( 27^1)
Now
27^(996*6) = (27^6)* (27^6)* (27^6)…. 996 times
=1*1*1….996 times =1 (mod 7)

That is we replaced each of 27^6 by 1 as 27^6 =1 (mod 7)

So what are we left with is

(27^(996*6) ) * ( 27^1) =1 * (27^1) (mod 7) = 27 (mod 7)

And 27 leaves remainder 6 when divided by 7
So 27 =6(mod 7)
Therefore answer is 6.
Try this trick for more problems.