Fermat's Little Theorem

What is Fermat's Little Theorem?

If $ p $ is a prime number and $ a $ is an integer not divisible by $ p $, then the following congruence holds: $$ a^{p-1} \equiv 1 \mod p $$

This is the standard form of the theorem, where $ p $ and $ a $ are coprime integers, meaning they have no common factors other than 1, i.e., $ \gcd(a, p) = 1 $.

Note: In the context of Fermat’s Little Theorem, saying that $ a $ and $ p $ are coprime is the same as saying that $ a $ is not divisible by $ p $. Since $ p $ is prime, its only divisors are 1 and itself.

There is also a more general form of the theorem that applies to all integers $ a $, including those divisible by $ p $:

$$ a^p \equiv a \mod p $$

This result follows directly from multiplying both sides of the congruence $ a^{p-1} \equiv 1 \mod p $ by $ a $:

$$ a^{p-1} \cdot a \equiv 1 \cdot a \mod p $$

$$ a^p \equiv a \mod p $$

If $ a $ is divisible by $ p $, then both sides of the congruence are 0 modulo $ p $, making the statement trivially true.

Example

Let’s consider a case where the modulus is the prime number $ p=2 $, and $ a = 5 $, which is not divisible by $ p $. According to the theorem:

$$ 5^{2-1} \equiv 1 \mod 2 $$

$$ 5 \equiv 1 \mod 2 $$

Since 5 divided by 2 leaves a remainder of 1, the congruence holds.

Example 2

Now, let's take the prime $ p=2 $ and the integer $ a=6 $, which is divisible by $ p $.

In this case, we use the general formula:

$$ 6^2 \equiv 6 \mod 2 $$

$$ 36 \equiv 6 \mod 2 $$

Since both 36 and 6 leave a remainder of 0 when divided by 2, they are congruent modulo 2.

Why is Fermat’s Little Theorem useful? It simplifies exponentiation in modular arithmetic, especially when dealing with large numbers. The only limitation is that it applies only when the modulus is a prime number. This makes it particularly valuable in primality testing and cryptographic algorithms such as RSA encryption.

Additional Examples

Consider the integer $ a=4 $ and the prime $ p=3 $.

These numbers are coprime since their greatest common divisor is 1:

$$ \gcd(4,3) = 1 $$

By Fermat’s Little Theorem:

$$ a^{p-1} = 4^{3-1} = 4^2 = 16 $$

Dividing 16 by 3 leaves a remainder of 1.

Thus, 16 is congruent to 1 modulo 3:

$$ 16 \equiv 1 \mod 3 $$

Example 2

Let's find the remainder when dividing \( 5^{19} \) by 3:

$$ 5^{19} \mod 3 $$

We can rewrite the expression in an equivalent form:

$$ (5^6)^3 \cdot 5 \mod 3 $$

Explanation: Dividing the exponent 19 by 3 gives a quotient of 6 and a remainder of 1.

Now, we apply Fermat’s Little Theorem, since \( (5^6)^3 \) has an exponent that matches the modulus 3:

$$ 5^6 \cdot 5 \mod 3 $$

$$ 5^7 \mod 3 $$

Next, we simplify the congruence further to apply Fermat’s theorem again:

$$ (5^2)^3 \cdot 5 \mod 3 $$

Explanation: Dividing the exponent 7 by 3 gives a quotient of 2 and a remainder of 1.

Applying Fermat’s theorem once more:

$$ 5^2 \cdot 5 \mod 3 $$

$$ 5^3 \mod 3 $$

Using Fermat’s theorem again, we get:

$$ 5 \mod 3 $$

Example 3

Now, let's determine the remainder when dividing \( 4526^{236} \) by 7.

First, we simplify the base by reducing it modulo 7:

$$ 4^{236} \mod 7 $$

Explanation: Since 4526 divided by 7 leaves a remainder of 4, we can replace 4526 with \( 4 \mod 7 \), which is equivalent:

$$ 4526 \equiv 4 \mod 7 $$

Rewriting the congruence in a more convenient form:

$$ (4^{33})^7 \cdot 4^5 \mod 7 $$

Explanation: Dividing 236 by 7 gives a quotient of 33 and a remainder of 5.

Applying Fermat’s Little Theorem:

$$ 4^{33} \cdot 4^5 \mod 7 $$

$$ 4^{38} \mod 7 $$

We simplify again:

$$ (4^5)^7 \cdot 4^3 \mod 7 $$

Explanation: Dividing 38 by 7 gives a quotient of 5 and a remainder of 3.

Applying Fermat’s theorem:

$$ 4^5 \cdot 4^3 \mod 7 $$

$$ 4^8 \mod 7 $$

Further simplification:

$$ 4^7 \cdot 4 \mod 7 $$

Explanation: Dividing 8 by 7 gives a quotient of 1 and a remainder of 1.

Applying Fermat’s theorem once more:

$$ 4 \cdot 4 \mod 7 $$

$$ 4^2 \mod 7 $$

Since the exponent is now small, we compute \( 4^2 \mod 7 \) directly:

$$ 16 \mod 7 $$

$$ 2 \mod 7 $$

Thus, the remainder when dividing \( 4526^{236} \) by 7 is 2.

Fermat’s Little Theorem and Prime Numbers

If \( p \) is a prime number, Fermat’s theorem states that for any integer \( a \) not divisible by \( p \), the following congruence holds:

$$ a^{p-1} \equiv 1 \mod p $$

On the other hand, if \( p \) is composite, the relationship changes to:

$$ a^p \equiv a \mod p $$

Now, let’s explore why this is true.

Understanding the Theorem

The key idea behind this result lies in modular arithmetic and the structure of multiplicative groups.

When working with a prime number \( p \), the integers from 1 to \( p-1 \) (excluding zero) form a multiplicative group modulo \( p \), denoted as \( (\mathbb{Z}^*_p, \cdot ) \).

In simple terms, this means every nonzero number in this set has a multiplicative inverse, and the order of the group—the number of elements—is \( p-1 \).

An important theorem in algebra states that for any element \( a \) in a group, the order of the element—the smallest exponent that makes it equal to 1—must divide the order of the group.

In this case, that means:

\[ a^{p-1} \equiv 1 \ (\text{mod} \ p) \]

Since the group's order is \( p-1 \), any exponent that results in 1 must be a multiple of this value.

Therefore, raising any element of the group to the power of \( p-1 \) always gives 1 modulo \( p \):

$$ a^{p-1} \equiv 1 \mod p $$

This explains why Fermat’s theorem holds when \( p \) is prime.

Note. This property holds only for prime numbers. However, some composite numbers also satisfy it for certain bases \( a \), mimicking prime numbers. For this reason, they are known as Fermat pseudoprimes.

Example

Let’s use a concrete example to make things clearer. Consider the small prime number \( p = 7 \).

We take all the integers from 1 to \( p-1 \):

\[ 1, 2, 3, 4, 5, 6 \]

These numbers form a multiplicative group modulo 7. That is, each number has an inverse, and multiplying any two of them always results in another number within the set.

The key observation is that when these numbers are raised to successive powers, they begin to repeat in cycles.

The longest possible cycle—the number of steps before the sequence wraps back to 1—is exactly \( p-1 \), which is the order of the group.

Let’s check this with \( a = 3 \):

Exponent	Value mod 7
\( 3^1 \)	3 ≡ 3 (mod 7)
\( 3^2 \)	9 ≡ 2 (mod 7)
\( 3^3 \)	27 ≡ 6 (mod 7)
\( 3^4 \)	81 ≡ 4 (mod 7)
\( 3^5 \)	243 ≡ 5 (mod 7)
\( 3^6 \)	729 ≡ 1 (mod 7)

After 6 steps (i.e., \( p-1 = 6 \)), we cycle back to 1. This isn’t a coincidence—it happens for any integer not divisible by \( p \).

Thus, the order of this element (\( a=3 \)) is 6, which is a divisor of the group order (also 6).

Note: If instead we use a composite number as the modulus (e.g., 8 instead of 7), this property no longer holds because some numbers lose their multiplicative inverses.

Now, let’s see what happens with \( a = 2 \):

Exponent	Value mod 7
\( 2^1 \)	2 ≡ 2 (mod 7)
\( 2^2 \)	4 ≡ 4 (mod 7)
\( 2^3 \)	8 ≡ 1 (mod 7)
\( 2^4 \)	16 ≡ 2 (mod 7)
\( 2^5 \)	32 ≡ 4 (mod 7)
\( 2^6 \)	64 ≡ 1 (mod 7)

Here, the order of the element (\( a=2 \)) is 3, meaning it takes three steps to return to 1 modulo 7.

Notice that the element’s order (3) is a divisor of the group order (6), which means that raising \( 2^6 \) still results in 1 modulo 7.

And this holds for all elements in the group.