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(modp)$. 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 $ax+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(modp)$ 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(modp)$, which by induction has at most $n-1$ solutions. $\blacksquare$

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

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

Example: Solve $x^2-1(mod77)$.

$x^2-1$ has the solutions $\pm 1(mod7)$ and $\pm 1(mod11)$ (since they are both prime), thus the solutions modulo $77$ are the ones corresponding to:

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(mod2)$.) 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.

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(modp)$. 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(modp)$ 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

if and only if $p$ is prime.

Proof:

and the result follows from Wilson’s Theorem. $\blacksquare$