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