Roots of Polynomials

Example: What are the roots of \(x^2 - 1\) modulo some prime \(p\)?

Clearly, \(x = \pm 1\) works, but are there any other solutions?

Suppose \((x+1)(x-1)=0 \pmod{p}\). As \(p\) is prime, we see \(p\) divides \((x+1)\) or \(p\) divides \((x-1)\). These cases correspond to the solutions we already have, so there are no more solutions.

More generally, we have the following:

Theorem: Let \(f(x)\) be a polynomial over \(\mathbb{Z}_p\) of degree \(n\). Then \(f(x)\) has at most \(n\) roots.

Proof: We induct. For degree 1 polynomials \(a x + b\), we have the unique root \(x = -b a^{-1}\).

Suppose \(f(x)\) is a degree \(n\) with at least one root \(a\). Then write \(f(x) = (x-a)g(x)\) where \(g(x)\) has degree \(n-1\). Now \(f(x) = 0 \pmod{p}\) means \((x-a) g(x)\) is a multiple of \(p\).

Since \(p\) is prime, \(p\) divides \((x-a)\), or \(p\) divides \(g(x)\). In the former case, we have the root \(a\), and the latter case is equivalent to saying \(g(x) = 0 \pmod{p}\), which by induction has at most \(n-1\) solutions.∎

Composite Moduli

Let \(n\) be a product of distinct primes: \(n = p_1 ... p_k\). The Chinese Remainder Theorem implies we can solve a polynomial \(f(x)\) over each \(\mathbb{Z}_{p_i}\) and then combine the roots together to find the solutions modulo \(n\). This is because a root \(a\) of \(f(x)\) in \(\mathbb{Z}_n\) corresponds to

\[ (a_1,...,a_k) \in \mathbb{Z}_{p_1} \times ... \times \mathbb{Z}_{p_k} \]

where each \(a_i\) is a root of \(f(x)\) in \(\mathbb{Z}_{p_i}\).

Example: Solve \(x^2 - 1 \pmod{77}\).

\(x^2 - 1\) has the solutions \(\pm 1 \pmod{7}\) and \(\pm 1 \pmod{11}\) (since they are both prime), thus the solutions modulo \(77\) are the ones corresponding to:

  • \(x = 1 \pmod{7}, x = 1 \pmod{11}\): this is \(x = 1 \pmod{77}\)

  • \(x = 1 \pmod{7}, x = -1 \pmod{11}\): this is \(x = 43 \pmod{77}\)

  • \(x = -1 \pmod{7}, x = 1 \pmod{11}\): this is \(x = 34 \pmod{77}\)

  • \(x = -1 \pmod{7}, x = -1 \pmod{11}\): this is \(x = -1 (= 76) \pmod{77}\)

Generalizing the last example, whenever \(N\) is the product of two distinct odd primes we always have four square roots of unity. (When one of the primes is \(2\) we have a degenerate case because \(1 = -1 \pmod{2}\).) An interesting fact is that if we are told one of the non-trivial square roots, we can easily factorize \(N\) (how?).

In order to describe the solutions of a polynomial \(f(x)\) over \(\mathbb{Z}_n\) for any \(n\), we need to find the roots of \(f(x)\) over \(\mathbb{Z}_{p^k}\) for prime powers \(p^k\). We shall leave this for later.

Wilson’s Theorem

Since the only square roots of 1 modulo \(p\) are \(\pm 1\) for a prime \(p\), for any element \(a \in \mathbb{Z}_p^*\), we have \(a \ne a^{-1}\) unless \(a = \pm 1\). Thus in the list \(2, 3, ..., p - 2\) we have each element and its inverse exactly once, hence \((p-1)! = -1 \pmod{p}\). On the other hand when \(p\) is composite, \((p-1)!\) is divisible by all the proper factors of \(p\) so we have:

Theorem: For an integer \(p > 1\) we have \((p-1)! = -1 \pmod {p}\) if and only if \(p\) is prime.

At first glance, this seems like a good way to tell if a given number is prime but unfortunately there is no known fast way to compute \((p-1)!\).

Wilson’s Theorem can be used to derive similar conditions:

Theorem: For an odd integer \(p > 1\), let \(r = (p-1)/2\). Then

\[ (-1)^r (r!)^2 = -1 \pmod {p} \]

if and only if \(p\) is prime.

Proof:

\[ \begin{aligned} (p-1)! &=& 1(p-1)2(p-2) ...((p-1)/2)((p+1)/2) \\ &=& 1(-1) 2(-2)...r(-r) \\ &=& (-1)^r (r!)^2 \end{aligned} \]

and the result follows from Wilson’s Theorem.∎


Ben Lynn blynn@cs.stanford.edu 💡