Polynomial Version of Fermat’s Little Theorem

The polynomial version of Fermat’s Little Theorem states that if $ n $ is a prime number, then for any integer $ a $ coprime to $ n $, the following identity holds:

\[(x + a)^n \equiv x^n + a \pmod{n}\]

This is a natural extension of the classic Fermat’s Little Theorem, which asserts that for any prime $ p $ and any integer $ a $:

\[ a^p \equiv a \pmod{p} \]

This property is widely used in primality testing since any number that fails to satisfy it is guaranteed to be composite.

The key idea is that instead of working with individual numbers, we can generalize the theorem to polynomials.

If $ n $ is prime, then for any integer $ a $, the following identity holds universally:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

This is the polynomial analogue of Fermat’s Little Theorem.

If we encounter a number $ n $ that fails to satisfy this identity for some value of $ a $, then $ n $ is certainly composite.
Conversely, if the identity holds, then $ n $ might be prime—but further tests are required, as certain composite numbers can still satisfy the equation for specific choices of $ a $.

Note: In essence, if $ n $ is prime, the polynomial $ (x + a)^n $, when reduced modulo $ n $, simplifies neatly to $ x^n + a $ without introducing any unexpected coefficients. This mirrors the behavior of Fermat’s Little Theorem for integers, extending its scope to polynomials.

This principle underpins the AKS primality test, which employs a more refined version of the theorem to determine whether a number is prime.

A Concrete Example
A Fast Computation Technique

A Concrete Example

Let’s take $ n = 5 $ (a prime number) and choose $ a = 2 $. We consider the polynomial:

\[ (x + 2)^5 \]

Expanding it using the Binomial Theorem:

\[ (x + a)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} a^k \]

For our case, $ a=2 $ and $ n=5 $, so we expand:

\[ (x + 2)^5 = x^5 + \binom{5}{1} x^4 \cdot 2 + \binom{5}{2} x^3 \cdot 2^2 + \binom{5}{3} x^2 \cdot 2^3 + \binom{5}{4} x \cdot 2^4 + \binom{5}{5} \cdot 2^5 \]

Note: The binomial coefficient is computed using: \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \]

Now, let’s compute the coefficients modulo $ 5 $:

$ \binom{5}{0} = \frac{5!}{0!(5-0)!} = 1 \equiv 1 \pmod{5} $
$ \binom{5}{1} = \frac{5!}{1!(5-1)!} = 5 \equiv 0 \pmod{5} $
$ \binom{5}{2} = \frac{5!}{2!(5-2)!} = 10 \equiv 0 \pmod{5} $
$ \binom{5}{3} = \frac{5!}{3!(5-3)!} = 10 \equiv 0 \pmod{5} $
$ \binom{5}{4} = \frac{5!}{4!(5-4)!} = 5 \equiv 0 \pmod{5} $
$ \binom{5}{5} = \frac{5!}{5!(5-5)!} = 1 \equiv 1 \pmod{5} $

Substituting these values back into our expansion:

\[ (x + 2)^5 = 1 \cdot x^5 + 0 \cdot x^4 \cdot 2 + 0 \cdot x^3 \cdot 2^2 + 0 \cdot x^2 \cdot 2^3 + 0 \cdot x \cdot 2^4 + 1 \cdot 2^5 \]

\[ (x + 2)^5 \equiv x^5 + 2^5 \pmod{5} \]

\[ (x + 2)^5 \equiv x^5 + 2 \pmod{5} \]

This perfectly matches the polynomial identity:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

Thus, we’ve confirmed that when $ n $ is prime, all intermediate terms vanish modulo $ n $, leaving only $ x^n + a $, exactly as predicted by the theorem.

Example 2

Now, let’s examine what happens when $ n = 9 $, which is not a prime number. Unlike in the prime case, the polynomial version of Fermat’s Little Theorem is no longer guaranteed to hold.

In other words, the identity might fail for certain values of $ a $. Let’s put this to the test with a concrete example:

\[ (x + a)^9 \equiv x^9 + a \pmod{9} \]

We expand $ (x + 2)^9 $ using the Binomial Theorem:

\[ (x + 2)^9 = \sum_{k=0}^{9} \binom{9}{k} x^{9-k} 2^k \]

Now, let’s compute the binomial coefficients modulo 9:

$ \binom{9}{0} = 1 $
$ \binom{9}{1} = 9 \equiv 0 \pmod{9} $
$ \binom{9}{2} = 36 \equiv 0 \pmod{9} $
$ \binom{9}{3} = 84 \equiv 3 \pmod{9} $
$ \binom{9}{4} = 126 \equiv 0 \pmod{9} $
$ \binom{9}{5} = 126 \equiv 0 \pmod{9} $
$ \binom{9}{6} = 84 \equiv 3 \pmod{9} $
$ \binom{9}{7} = 36 \equiv 0 \pmod{9} $
$ \binom{9}{8} = 9 \equiv 0 \pmod{9} $
$ \binom{9}{9} = 1 $

Substituting these values, we obtain:

\[ (x + 2)^9 = x^9 + 0x^8 + 0x^7 + 3x^6 \cdot 2^3 + 0x^5 + 0x^4 + 3x^3 \cdot 2^6 + 0x^2 + 0x + 2^9 \]

\[ (x + 2)^9 = x^9 + 3x^6 \cdot 8 + 3x^3 \cdot 64 + 512 \]

Reducing modulo 9:

$ 3 \cdot 8 = 24 \equiv 6 \pmod{9} $
$ 3 \cdot 64 = 192 \equiv 3 \pmod{9} $
$ 512 \equiv 8 \pmod{9} $

So we end up with:

\[ (x + 2)^9 \equiv x^9 + 6x^6 + 3x^3 + 8 \pmod{9} \]

Unlike in the prime case, additional terms appear ($ 6x^6 + 3x^3 + 8 $), meaning the identity does not hold:

\[ (x + 2)^9 \not\equiv x^9 + 2 \pmod{9} \]

This confirms that the polynomial version of Fermat’s Little Theorem does not hold for $ n = 9 $, proving once again that $ 9 $ is composite.

Note: If $ n $ were prime, every binomial coefficient $ \binom{n}{k} $ (for $ 1 \leq k \leq n-1 $) would be divisible by $ n $, reducing to zero modulo $ n $ and leaving only $ x^n + a $. However, since $ n = 9 $ is composite, some coefficients remain nonzero modulo 9, breaking the identity.

A Fast Computation Technique

The original primality test involves checking the condition:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

While mathematically sound, this approach is computationally expensive because the polynomial $ (x + a)^n $ has $ n+1 $ coefficients—an unmanageable number for large $ n $.

Moreover, each binomial coefficient $ \binom{n}{k} $ must be computed modulo $ n $, and expanding the polynomial itself is costly in terms of time and resources.

How can we reduce the number of coefficients to check?

The key to speeding up the test is to work within a quotient ring, specifically $ \mathbb{Z}_n[x] / (x^r - 1) $, rather than in $ \mathbb{Z}_n[x] $ directly.

This allows us to verify the condition on a smaller subset of coefficients rather than all of them.

In other words, instead of checking:

\[ (x + a)^n \equiv x^n + a \pmod{n} \]

for the entire polynomial in $ \mathbb{Z}_n[x] $, we only verify it modulo a simpler polynomial:

\[ (x + a)^n \equiv x^n + a \quad \text{in } \mathbb{Z}_n[x] / (x^r - 1) \]

where $ r $ is a much smaller value than $ n $, chosen strategically.

Why does this help? Instead of computing all $ n+1 $ coefficients of $ (x + a)^n $, we only compute $ r $ of them. This drastically reduces the computational burden. If $ r $ is small relative to $ n $, the test runs in polynomial time with respect to $ \log n $, making it much more practical.

How do we choose $ r $?

To find a small $ r $ that preserves the correctness of the test, we follow a simple approach:

Pick a candidate $ r $, typically a small value like $ r = 2, 3, 4, \dots $, ensuring that $ r < n $.
Compute the order of $ n $ modulo $ r $, looking for the smallest $ k $ such that: \[ n^k \equiv 1 \pmod{r} \]
If $ k $ is small, $ r $ is a good choice; otherwise, we try a different $ r $.

An alternative approach. If $ n $ is very large, we can prove that there exists a relatively small $ r $ (dependent on $ \log n $) such that, if the equation holds for sufficiently many values of $ a $, then $ n $ must be prime. Specifically, we have:

\[ r \leq \lfloor 16 \log_2^2 n \rfloor + 1 \]

This formula is particularly useful for large values of $ n $ since it guarantees that $ r $ remains significantly smaller than $ n $, making computations more efficient. However, for smaller values of $ n $, the formula might return an $ r $ larger than $ n $, which would render it useless in practice.

Practical Example

Let’s check whether $ n = 37 $ is prime. Instead of expanding:

\[ (x + a)^{37} \]

we verify only:

\[ (x + a)^{37} \equiv x^{37} + a \quad \text{in } \mathbb{Z}_{37}[x] / (x^r - 1) \]

Using the logarithmic formula to estimate $ r $:

$$ r \approx \lfloor 16 \log_2^2(37) \rfloor + 1 \approx 435 $$

However, since $ r = 435 $ is greater than $ n = 37 $, it’s impractical to use.

Instead, we manually select a smaller $ r $, say $ r = 24 $:

\[(x + a)^{37} \equiv x^{37} + a \quad \text{in } \mathbb{Z}_{37}[x] / (x^{24} - 1)\]

This means we compute $ (x + a)^{37} $ modulo 37 and modulo the polynomial $ x^{24} - 1 $.

Why choose $ r = 24 $? To find a suitable $ r $ for $ n = 37 $, we determine the multiplicative order of $ 37 $ modulo $ 24 $. It turns out that $ k = 2 $ because:

\[ 37^1 \equiv 13 \pmod{24}, \quad 37^2 \equiv 1 \pmod{24} \]

Since $ k = 2 $ is much smaller than $ r = 24 $, this is a good choice.

Working in $ \mathbb{Z}_{37}[x] / (x^{24} - 1) $, we reduce all exponents modulo 24:

\[ x^{37} = x^{(24 + 13)} = x^{13} \quad \text{(since $ x^{24} \equiv 1 $)} \]

Thus, the equation simplifies to:

\[ (x + a)^{37} \equiv x^{13} + a \pmod{37}, \quad \text{in } \mathbb{Z}_{37}[x] / (x^{24} - 1) \]

Now, we check this identity for several values of $ a $ coprime to $ 37 $. Typically, small values like $ a = 1, 2, 3 $ are chosen.

For example, with $ a = 1 $:

\[ (x + 1)^{37} \equiv x^{13} + 1 \pmod{37} \]

If this equation holds for a sufficient number of values of $ a $, we can conclude that $ 37 $ is prime.

By strategically choosing $ r $, we’ve significantly reduced the number of coefficients to check, streamlining the test without sacrificing correctness.

This dramatically lowers the computational cost.

Key takeaway. The fundamental idea is to reduce the number of coefficients from $ n+1 $ to a much smaller $ r $, making the test polynomial in $ \log n $ instead of exponential. This is the core principle behind the AKS algorithm, which enables a deterministic and efficient primality test.

And so on.