Fermat's Little Theorem & Applications Cheat Sheet

Fermat's Little Theorem is a key result in number theory that helps simplify powers in modular arithmetic. This cheat sheet covers the theorem, when it applies, and how it is used to find remainders and modular inverses. Students need it because large exponent problems become manageable when powers repeat in predictable cycles.

It is especially useful for contest math, cryptography basics, and advanced algebra topics.

The main idea is that if $p$ is prime and $a$ is not divisible by $p$ , then $a^{p-1} \equiv 1 \pmod{p}$ . This means exponents can often be reduced modulo $p-1$ when working mod $p$ . A related form says $a^p \equiv a \pmod{p}$ for any integer $a$ .

Applications include computing large remainders, checking divisibility patterns, and finding inverses using $a^{-1} \equiv a^{p-2} \pmod{p}$ .

Key Facts

If $p$ is prime and $\gcd(a,p)=1$ , then Fermat's Little Theorem states $a^{p-1} \equiv 1 \pmod{p}$ .
For any integer $a$ and prime $p$ , the equivalent form $a^p \equiv a \pmod{p}$ is always true.
When $p$ is prime and $\gcd(a,p)=1$ , exponents can be reduced using $a^n \equiv a^{r} \pmod{p}$ where $r \equiv n \pmod{p-1}$ .
If $p$ is prime and $p \nmid a$ , the modular inverse of $a$ modulo $p$ is $a^{-1} \equiv a^{p-2} \pmod{p}$ .
The condition $\gcd(a,p)=1$ is required for the form $a^{p-1} \equiv 1 \pmod{p}$ .
If $a \equiv b \pmod{m}$ , then $a^n \equiv b^n \pmod{m}$ for any positive integer $n$ .
To compute a large power like $a^n \pmod{p}$ , first reduce $a$ modulo $p$ , then reduce $n$ modulo $p-1$ when $p$ is prime and $p \nmid a$ .
Fermat's Little Theorem does not prove that $p$ is prime just because $a^{p-1} \equiv 1 \pmod{p}$ holds for one value of $a$ .

Vocabulary

Prime modulus: A modulus $p$ that is a prime number, which is required for the standard form of Fermat's Little Theorem.
Congruence: A statement $a \equiv b \pmod{m}$ meaning that $a$ and $b$ have the same remainder when divided by $m$ .
Relatively prime: Two integers $a$ and $b$ are relatively prime when $\gcd(a,b)=1$ .
Modular inverse: The modular inverse of $a$ modulo $m$ is a number $x$ such that $ax \equiv 1 \pmod{m}$ .
Exponent reduction: Exponent reduction is the process of replacing a large exponent with a smaller congruent exponent, often using $n \equiv r \pmod{p-1}$ .
Remainder class: A remainder class is the set of all integers that are congruent to the same value modulo $m$ .

Common Mistakes to Avoid

Using $a^{p-1} \equiv 1 \pmod{p}$ when $p \mid a$ is wrong because the theorem requires $\gcd(a,p)=1$ for that form.
Applying Fermat's Little Theorem with a composite modulus is wrong because $a^{p-1} \equiv 1 \pmod{p}$ is guaranteed only when $p$ is prime.
Reducing the exponent modulo $p$ instead of modulo $p-1$ is wrong because the power cycle from Fermat's Little Theorem has length dividing $p-1$ .
Changing $a^0$ to $0$ is wrong because $a^0=1$ for $a \neq 0$ , so an exponent reduction that gives $r=0$ usually means $a^n \equiv 1 \pmod{p}$ .
Assuming one successful Fermat test proves primality is wrong because some composite numbers can satisfy $a^{n-1} \equiv 1 \pmod{n}$ for certain bases $a$ .

Practice Questions

1 Find the remainder when $7^{100}$ is divided by $13$ .
2 Find the modular inverse of $8$ modulo $17$ using Fermat's Little Theorem.
3 Compute $3^{2025} \pmod{11}$ .
4 Explain why Fermat's Little Theorem can be used to reduce the exponent in $5^{1234} \pmod{19}$ , but not directly in $6^{1234} \pmod{21}$ .

Understanding Fermat's Little Theorem & Applications

A useful way to understand the result is to look at multiplication by a number modulo a prime. Take a nonzero remainder, such as three modulo seven, and multiply every nonzero remainder by three. The results are three, six, two, five, one, and four.

None repeat before every possible nonzero remainder has appeared. This happens because a repeated result would mean that two different numbers have the same remainder after multiplication by three. Since three has an inverse modulo seven, that would force the original numbers to have been equal.

Thus multiplication simply rearranges the nonzero remainders. Comparing the product before and after this rearrangement leads to the power rule.

The repeating pattern of powers can be shorter than the length promised by the theorem. For example, powers of two modulo seven go two, four, one, then repeat. The cycle length is three, even though the prime minus one is six.

This shorter length is called the order of the number modulo the prime. Reducing an exponent by the prime minus one is always safe under the required conditions, but finding the shorter cycle can make hand calculations faster.

Students should first list a few powers when the modulus is small. This reveals patterns and gives a check on any exponent reduction.

Modular inverses turn division into multiplication. Ordinary division is not usually meaningful when only remainders matter. Instead, to divide by a number, find a number whose product with it leaves remainder one.

For instance, the inverse of three modulo seven is five because three times five leaves remainder one upon division by seven. Therefore a congruence involving three times a value can be solved by multiplying both sides by five.

The power method for inverses works for prime moduli, though the extended Euclidean algorithm is often quicker for actual calculations. That algorithm works whenever the number and modulus have greatest common divisor one, even if the modulus is not prime.

The prime condition deserves careful attention. With a composite modulus, nonzero remainders can fail to have inverses. For example, two times three is zero modulo six, even though neither factor is zero modulo six.

This kind of zero product cannot happen modulo a prime. It explains why prime moduli behave so cleanly. In cryptography, large prime numbers are chosen partly because inverse calculations are reliable in these systems.

However, the theorem is not a shortcut for declaring a number prime. Some composite numbers pass the power test for certain bases.

When solving school problems, state the modulus, check whether it is prime, reduce the base first, then decide whether the exponent rule is allowed. These habits prevent most common errors.

Sign in to save

Sign in to save

Fermat's Little Theorem & Applications Cheat Sheet

Related Tools

Related Labs

Related Worksheets

Related Infographics

Study as Flashcards

Key Facts

Vocabulary

Common Mistakes to Avoid

Practice Questions

Understanding Fermat's Little Theorem & Applications