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 a^p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

a^p ≡ a (mod  p).

1. Using the Fermat’s little theorum for modular arithmetic, we know that a^p ≡ 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 2²²⁰⁰⁶ (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 2² ≡ 1 (mod  3)

which means

2⁽2²⁰⁰⁶) ≡ 1 (mod  3) i.e., (2²)²²⁰⁰⁵ ≡ 1⁽2²⁰⁰⁵) (mod  3)

So, the solution is 2²²⁰⁰⁶ (mod  3) ≡ 1 (mod  3)

Question: Is the difference between 5³⁰⁰⁰⁰ and 6¹²³⁴⁵⁶ 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)¹⁰⁰⁰ = (5³⁰)¹⁰⁰⁰

Rewriting the modular equation similar to Fermat’s little theorum (5³⁰)¹⁰⁰⁰ ≡ 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 = (6⁶)(6³⁰)⁴¹¹⁵

Using the Fermats little theorum (6³⁰)⁴¹¹⁵ ≡ 1 (mod  31)

That leaves, (6⁶) (mod  31) to be computed.

Breaking this further,

6⁶ ≡ (6²)(6²)(6²) (mod  31)

6⁶ ≡ (5)(5)(5) (mod  31)

6⁶ ≡ 125 (mod  31)

6⁶ ≡ 1 (mod  31)

So the difference between 5³⁰⁰⁰⁰ and 6¹²³⁴⁵⁶ 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.

@article{gopal2022usingfermatslittletheorumformodulararithmetic,
  title   = {Using Fermat’s little theorum for modular arithmetic},
  author  = {Senthilkumar Gopal},
  journal = {sengopal.me},
  year    = {2022},
  month   = {Jan},
  url     = {https://sengopal.me/posts/using-fermats-little-theorum-for-modular-arithmetic}
}