Senthilkumar Gopal

Musings of a machine learning engineer

Using Fermat’s little theorum for modular arithmetic


Fermat’s little theorum is a fundamental theorum for any modular arithmetic problems and provides a neat little trick for finding the reminder for division by large numbers.

From Wikipedia

Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

ap ≡ a (mod  p).

  1. Using the Fermat’s little theorum for modular arithmetic, we know that ap ≡ a(modp)
  2. Dividing by a on both sides, a(p−1) ≡ 1 (mod  p) for all 1 ≤ a ≤ p − 1
  3. a(p−1) ≡ 1 (mod  p) if a (mod  p) ≠ 0
  4. a(p−1)k ≡ 1 (mod  p) if a (mod  p) ≠ 0 and k is a natural number.

Test for primality

r is a prime number iff a(r−1) ≡ 1 (mod  r) for 1 ≤ a ≤ r − 1

Question: What is 222006 (mod  3)

From Fermat’s little theorum we know that a(p−1) ≡ 1 (mod  p) if a (mod  p) ≠ 0

The trick here is to make the power same as (p−1)

So we can formulate that,

2(3−1) ≡ 1 (mod  3) which becomes 22 ≡ 1 (mod  3)

which means

2(22006) ≡ 1 (mod  3) i.e., (22)22005 ≡ 1(22005) (mod  3)

So, the solution is 222006 (mod  3) ≡ 1 (mod  3)

Question: Is the difference between 530000 and 6123456 divisible by 31

From Fermat’s little theorum we know that a(p−1)k ≡ 1 (mod  p) if a (mod  p) ≠ 0 and k is a natural number.

The trick here is to make the power same as (p−1)

we know that, 5(31−1)1000 = (530)1000

Rewriting the modular equation similar to Fermat’s little theorum (530)1000 ≡ 1 (mod  31)

For the second part, dividing 12346 by 30 gives a reminder of 6 and a divisor of 4115. So the second part of the equation can be rewritten as, 6123456 = (66)(630)4115

Using the Fermats little theorum (630)4115 ≡ 1 (mod  31)

That leaves, (66) (mod  31) to be computed.

Breaking this further,

66 ≡ (62)(62)(62) (mod  31)

66 ≡ (5)(5)(5) (mod  31)

66 ≡ 125 (mod  31)

66 ≡ 1 (mod  31)

So the difference between 530000 and 6123456 being divisible by 31 is simply written as, 1 (mod  31) − 1 (mod  31) = 0 (mod  31) which implies that it is indeed divisible by 31.