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⁽³⁻¹⁾ ≡ 1 (mod  3) which becomes 2² ≡ 1 (mod  3)

which means

2^(22006) ≡ 1 (mod  3) i.e., (2²)²²⁰⁰⁵ ≡ 1^(22005) (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)1000 = (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.