Fermat’s Little Theorem

students, imagine you want to check whether a huge number leaves a certain remainder when divided by a prime. Instead of calculating a giant power directly, Number Theory gives you a shortcut ⚡. That shortcut is Fermat’s Little Theorem, one of the most useful ideas in the topic of Fermat and Euler.

What you will learn

By the end of this lesson, students, you should be able to:

explain the main ideas and vocabulary behind Fermat’s Little Theorem,
use the theorem to simplify powers modulo a prime,
connect this theorem to Euler’s theorem and Euler’s phi function,
recognize why prime numbers are special in modular arithmetic,
support your work with examples and reasoning.

Fermat’s Little Theorem is not “little” because it is unimportant. It is called little because there is also Fermat’s Last Theorem. In practice, this theorem is a powerful tool for finding remainders, solving congruences, and understanding how powers behave in modular arithmetic 📘.

The big idea behind the theorem

In modular arithmetic, we care about remainders after division. We write $a \equiv b \pmod{n}$ to mean that $a$ and $b$ leave the same remainder when divided by $n$.

Fermat’s Little Theorem says that if $p$ is a prime number and $a$ is not divisible by $p$, then

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

This is the most common form of the theorem. There is also another useful version:

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

These two statements are closely related. If $a$ is not divisible by $p$, then multiplying both sides of $a^{p-1} \equiv 1 \pmod{p}$ by $a$ gives $a^p \equiv a \pmod{p}$. If $a$ is divisible by $p$, then $a^p$ and $a$ are both divisible by $p$, so the second form is still true.

The key condition is that $p$ must be prime. That is what makes this theorem so special. For composite numbers, the pattern is not always the same.

Understanding the vocabulary and notation

Let’s unpack the terms, students.

A prime number is a whole number greater than $1$ whose only positive divisors are $1$ and itself. Examples are $2, 3, 5, 7,$ and $11.

A number $a$ is coprime to $p$ if $\gcd(a,p)=1$. This means $a$ and $p$ share no common factor greater than $1$. When $p$ is prime, every number $a$ with $1 \le a \le p-1$ is automatically coprime to $p$.

A congruence such as $a \equiv b \pmod{p}$ means that $p$ divides the difference $a-b$.

The notation $a^{p-1}$ means $a$ multiplied by itself $p-1$ times. Fermat’s Little Theorem tells us that this big power has a very simple remainder modulo $p$.

For example, if $p=7$ and $a=3$, then the theorem says

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

This means the remainder when $3^6$ is divided by $7$ is $1$.

Why the theorem is true: a counting idea

There are several proofs of Fermat’s Little Theorem. Here is a high-school-friendly idea that shows why it makes sense.

Look at the numbers $1, 2, 3, \dots, p-1$ modulo a prime $p$. If $a$ is not divisible by $p$, then multiplying each of these numbers by $a$ gives

$$a, 2a, 3a, \dots, (p-1)a.$$

Now reduce each one modulo $p$. Because $p$ is prime and $a$ is not a multiple of $p$, none of these products is $0 \pmod{p}$, and they end up being a rearrangement of the numbers $1,2,3,\dots,p-1$.

So the product of the first list and the product of the second list have the same remainder modulo $p$:

$$1 \cdot 2 \cdot 3 \cdots (p-1) \equiv (a)(2a)(3a)\cdots((p-1)a) \pmod{p}.$$

This becomes

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

Because none of the numbers $1,2,\dots,p-1$ is divisible by $p$, the factorial $(p-1)!$ is not $0 \pmod{p}$, so it can be canceled in this modular setting. That leaves

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

This is the heart of the theorem. The argument shows that multiplication by $a$ simply shuffles the nonzero residues modulo a prime.

Using Fermat’s Little Theorem to simplify powers

One of the most important uses of the theorem is reducing huge exponents.

Suppose you want to find the remainder of $7^{100}$ when divided by $13$. Since $13$ is prime and $7$ is not divisible by $13$, Fermat’s Little Theorem says

$$7^{12} \equiv 1 \pmod{13}.$$

Now write $100$ as $12 \cdot 8 + 4$. Then

$$7^{100} = (7^{12})^8 \cdot 7^4.$$

Taking remainders modulo $13$ gives

$$7^{100} \equiv 1^8 \cdot 7^4 \equiv 7^4 \pmod{13}.$$

Now calculate step by step:

$$7^2=49 \equiv 10 \pmod{13}$$

and

$$7^4 \equiv 10^2 = 100 \equiv 9 \pmod{13}.$$

So the remainder is $9$.

This is much faster than trying to compute $7^{100}$ directly. ✅

Another example with a smaller prime

Let’s find the remainder of $2^{50}$ modulo $5$.

Since $5$ is prime and $2$ is not divisible by $5$,

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

Now $50=4\cdot 12+2$, so

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

So $2^{50}$ leaves remainder $4$ when divided by $5$.

You can also check this pattern directly:

$$2^1 \equiv 2 \pmod{5}, \quad 2^2 \equiv 4 \pmod{5}, \quad 2^3 \equiv 3 \pmod{5}, \quad 2^4 \equiv 1 \pmod{5}.$$

The remainders cycle every $4$ powers. That cycling is a common feature in modular arithmetic.

What happens when the base is divisible by the prime?

Fermat’s Little Theorem has a common condition: $a$ must not be divisible by $p$ in the form $a^{p-1} \equiv 1 \pmod{p}$. What if $a$ is divisible by $p$?

Take $a=p$. Then

$$p^{p-1} \equiv 0 \pmod{p}$$

and also

$$p \equiv 0 \pmod{p}.$$

So the statement $a^p \equiv a \pmod{p}$ still works. For example, with $p=7$ and $a=14$,

$$14^7 \equiv 0 \pmod{7}$$

and

$$14 \equiv 0 \pmod{7}.$$

So both sides match.

This shows why the theorem is often presented in two versions. The $a^{p-1} \equiv 1 \pmod{p}$ version is for nonzero residues modulo $p$, while $a^p \equiv a \pmod{p}$ works for all integers $a$.

Connection to Euler’s theorem and phi function

Fermat’s Little Theorem is actually a special case of Euler’s theorem.

Euler’s phi function, written $\varphi(n)$, counts how many positive integers from $1$ to $n$ are coprime to $n$.

Euler’s theorem says that if $\gcd(a,n)=1$, then

$$a^{\varphi(n)} \equiv 1 \pmod{n}.$$

Now look at a prime number $p$. Since every number from $1$ to $p-1$ is coprime to $p$,

$$\varphi(p)=p-1.$$

So Euler’s theorem becomes

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

which is exactly Fermat’s Little Theorem.

This connection matters because it shows that Fermat’s Little Theorem is part of a larger pattern in Number Theory. Prime numbers give the simplest case, and Euler’s theorem extends the idea to many composite moduli too.

Why this theorem matters in Number Theory

Fermat’s Little Theorem is useful for more than just calculation. It helps explain the structure of modular multiplication, supports faster computation, and appears in later topics such as cryptography 🔐.

For example, when large powers are used in encryption systems, repeated multiplication would be too slow. The theorem helps reduce the exponent and make computations manageable.

It also helps in proofs and problem solving. If you know that $a^{p-1} \equiv 1 \pmod{p}$, then you can often turn a difficult expression into a smaller one. That makes the theorem a practical tool as well as a theoretical result.

Conclusion

Fermat’s Little Theorem says that if $p$ is prime and $a$ is not divisible by $p$, then

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

It reveals a repeating pattern in powers modulo a prime, and it gives a fast way to simplify large exponents. students, you have seen how it works, why prime numbers matter, and how it connects directly to Euler’s theorem and $\varphi(n)$. This makes Fermat’s Little Theorem one of the central ideas in the study of Fermat and Euler.

Study Notes

Fermat’s Little Theorem is a rule about powers modulo a prime.
If $p$ is prime and $\gcd(a,p)=1$, then $a^{p-1} \equiv 1 \pmod{p}$.
Another form is $a^p \equiv a \pmod{p}$ for all integers $a$.
The theorem helps reduce large exponents by using $p-1$ as a cycle length.
A prime number has exactly $p-1$ nonzero residues modulo $p$, and multiplying by a number not divisible by $p$ rearranges them.
Euler’s theorem says that if $\gcd(a,n)=1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.
Fermat’s Little Theorem is the special case of Euler’s theorem when $n=p$ is prime and $\varphi(p)=p-1$.
This theorem is important in modular arithmetic, problem solving, and cryptography.