# 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 \gt 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 \gt 1$$, let $$r = (p-1)/2$$. Then

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

if and only if $$p$$ is prime.

Proof:

$\array { (p-1)! &=& 1(p-1)2(p-2) ...((p-1)/2)((p+1)/2) \\ &=& 1(-1) 2(-2)...r(-r) \\ &=& (-1)^r (r!)^2 }$

and the result follows from Wilson’s Theorem.∎

Ben Lynn blynn@cs.stanford.edu 💡