Fermat's Little Theorem Calculator

What Is Fermat's Little Theorem?

Fermat's Little Theorem is a cornerstone theorem in elementary number theory and modern cryptography. Stated by Pierre de Fermat in 1640, it asserts that if $p$ is a prime number and $a$ is any integer, then $a^p - a$ is always an integer multiple of $p$.

In modern modular arithmetic notation:

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

When $a$ is not divisible by $p$ (meaning $\gcd(a, p) = 1$), we can divide both sides of the congruence by $a$ to obtain the standard coprime form:

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

Key Applications of Fermat's Little Theorem

1. Simplifying Large Modular Exponentiation

When evaluating $a^b \pmod p$ where $p$ is prime and $b$ is a massive exponent, we can reduce the exponent modulo $p-1$:

$$b = q \cdot (p - 1) + r \implies a^b \equiv a^r \pmod p$$

For instance, computing $7^{50} \pmod{13}$: since $13 - 1 = 12$ and $50 \equiv 2 \pmod{12}$, we have $7^{50} \equiv 7^2 = 49 \equiv 10 \pmod{13}$.

2. Finding Modular Multiplicative Inverses

To find the modular inverse $a^{-1} \pmod p$ such that $a \cdot a^{-1} \equiv 1 \pmod p$:

$$a \cdot a^{p-2} = a^{p-1} \equiv 1 \pmod p \implies a^{-1} \equiv a^{p-2} \pmod p$$

This allows computing modular inverses directly with binary modular exponentiation without needing the Extended Euclidean Algorithm.

3. Fermat Primality Testing

Fermat's Little Theorem provides a fast probabilistic test for primality:

Choose a random base $a$ where $1 < a < n-1$.
Compute $a^{n-1} \pmod n$.
If the result is not 1, then $n$ is definitively composite, and $a$ is a Fermat witness.
If the result equals 1 for multiple randomly chosen bases, $n$ is considered a probable prime.

Conditions and Important Caveats

Modulus Must Be Prime: If $p$ is composite, the theorem does not necessarily hold. Euler's Totient Theorem generalizes Fermat's result to composite moduli: $a^{\phi(m)} \equiv 1 \pmod m$.
Carmichael Numbers: Certain composite numbers (such as $561 = 3 \times 11 \times 17$) satisfy $a^{n-1} \equiv 1 \pmod n$ for all coprime bases $a$. These are known as Carmichael numbers or Fermat pseudoprimes.

Related Mathematics and Number Theory Tools

Explore other cryptography and number theory tools:

Prime Factors Calculator: Find prime factorizations and factor trees.
Extended Euclidean Algorithm Calculator: Compute gcd and Bezout identity coefficients.
Modulo Calculator: Perform modular arithmetic and remainder operations.

Frequently Asked Questions

What is the difference between Fermat's Little Theorem and Fermat's Last Theorem?

Fermat's Little Theorem is a proven statement about modular arithmetic with primes ($a^{p-1} \equiv 1 \pmod p$). Fermat's Last Theorem is the famous statement that no three positive integers satisfy $a^n + b^n = c^n$ for any integer $n > 2$, which was proved by Andrew Wiles in 1994.

How do you compute a modular inverse using Fermat's Little Theorem?

If $p$ is prime and $\gcd(a, p) = 1$, rewrite $a^{p-1} \equiv 1 \pmod p$ as $a \cdot a^{p-2} \equiv 1 \pmod p$. Therefore, the modular inverse is $a^{-1} \equiv a^{p-2} \pmod p$.

What is a Fermat witness?

A Fermat witness is an integer $a$ for which $a^{n-1} \not\equiv 1 \pmod n$. The existence of a Fermat witness proves definitively that $n$ is a composite number.

Why does Fermat's theorem fail for composite numbers?

Fermat's Little Theorem relies on the structure of the multiplicative group modulo a prime $p$, which has order $p-1$. For composite moduli $m$, the group of units has order given by Euler's totient function $\phi(m) < m - 1$.

What is a Carmichael number?

A Carmichael number is an odd composite number $n$ that satisfies $a^{n-1} \equiv 1 \pmod n$ for every integer $a$ coprime to $n$. The smallest Carmichael number is $561$.

Report