- Wed 19 January 2022
- Math
- #math, #fermat, #modular-arithmetic, #algorithms, #learning

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*).

- Using the Fermat’s little theorum for modular arithmetic, we know
that
*a*^{p}≡*a*(*m**o**d**p*) - Dividing by a on both sides,
*a*^{(p−1)}≡ 1 (mod*p*) for all 1 ≤*a*≤*p*− 1 *a*^{(p−1)}≡ 1 (mod*p*) if*a*(mod*p*) ≠ 0*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^{22006} (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^{2} ≡ 1 (mod 3)

which means

2^{(22006)} ≡ 1 (mod 3)
i.e., (2^{2})^{22005} ≡ 1^{(22005)} (mod 3)

So, the solution is 2^{22006} (mod 3) ≡ 1 (mod 3)

#### Question:
Is the difference between 5^{30000} and 6^{123456} 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^{30})^{1000}

Rewriting the modular equation similar to Fermat’s little theorum
(5^{30})^{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 = (6^{6})(6^{30})^{4115}

Using the Fermats little theorum (6^{30})^{4115} ≡ 1 (mod 31)

That leaves, (6^{6}) (mod 31) to be computed.

Breaking this further,

6^{6} ≡ (6^{2})(6^{2})(6^{2}) (mod 31)

6^{6} ≡ (5)(5)(5) (mod 31)

6^{6} ≡ 125 (mod 31)

6^{6} ≡ 1 (mod 31)

So the difference between 5^{30000} and 6^{123456} 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.