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)(x1)=0 \pmod{p}$. As $p$ is prime, we see $p$ divides $(x+1)$ or $p$ divides $(x1)$. 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) = (xa)g(x)$ where $g(x)$ has degree $n1$. Now $f(x) = 0 \pmod{p}$ means $(xa) g(x)$ is a multiple of $p$.
Since $p$ is prime, $p$ divides $(xa)$, 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 $n1$ 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
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 nontrivial 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 $(p1)! = 1 \pmod{p}$. On the other hand when $p$ is composite, $(p1)!$ is divisible by all the proper factors of $p$ so we have:
Theorem: For an integer $p \gt 1$ we have $(p1)! = 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 $(p1)!$.
Wilson’s Theorem can be used to derive similar conditions:
Theorem: For an odd integer $p \gt 1$, let $r = (p1)/2$. Then
if and only if $p$ is prime.
Proof:
and the result follows from Wilson’s Theorem.∎