[Introduction to Number Theory Series Part 16] Why Does Fermat's Little Theorem Simplify Exponent Computations?

With congruence, modular arithmetic, inverses, and CRT in place, we are ready for a major theorem about powers modulo a prime.

What this post covers

• The statement of Fermat's little theorem
• The two common forms of the theorem
• Power-reduction examples
• The importance of the prime-modulus condition

Key terms

• Fermat's little theorem: the theorem that says a^{p-1} \equiv 1 \pmod p when p is prime and p does not divide a
• prime number: a natural number greater than 1 with only two positive divisors
• congruence: equality of remainder classes
• Euler's theorem: the general coprime version of Fermat's theorem

The theorem

If p is prime and p does not divide a, then

$$a^{p-1} \equiv 1 \pmod p.$$

A closely related version is

$$a^p \equiv a \pmod p.$$

For beginners, it helps to remember the distinction:

• a^{p-1} \equiv 1 \pmod p requires p \nmid a
• a^p \equiv a \pmod p is the all-integer version

So the second form is often easier to remember globally, while the first form is often the one used for power reduction when a is coprime to p.

Example 1: 3^{100} \pmod 7

Since 7 is prime,

$$3^6 \equiv 1 \pmod 7.$$

Now

$$100 = 6\cdot 16 + 4,$$

so

$$3^{100}=(3^6)^{16}3^4 \equiv 1^{16}3^4 \equiv 81 \equiv 4 \pmod 7.$$

Example 2: 2^{30} \pmod 5

Since 5 is prime,

$$2^4 \equiv 1 \pmod 5.$$

And

$$30 = 4\cdot 7 + 2,$$

so

$$2^{30}=(2^4)^7 2^2 \equiv 1^7\cdot 4 \equiv 4 \pmod 5.$$

Why do the conditions matter?

Fermat's little theorem is not a theorem for every modulus.

• the modulus must be prime
• for the a^{p-1} form, a must not be divisible by p

If the modulus is composite, we need a more general framework. That is where Euler's theorem enters.

Common mistakes

1. Using the theorem with a composite modulus

The standard theorem is about prime moduli.

2. Forgetting the condition p \nmid a

That condition matters for the a^{p-1} form.

3. Reducing the exponent but making an arithmetic mistake at the end

The final small power still needs to be computed carefully.

Wrap-up

Fermat's little theorem reduces large exponents modulo a prime by revealing a repeating structure in powers.

Next we generalize this from prime moduli to arbitrary moduli with Euler's totient function and Euler's theorem.