Fermat's Little Theorem & Applications Cheat Sheet

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$.