The idea behind $x^2 \equiv 1 \pmod p$ in the Miller-Rabin algorithm

Question

Trying to understand something about the Miller-Rabin algorithm.

What exactly is the implication of $x^2 \equiv 1 \pmod n$? I understand that it can be rearranged to $(x+1)(x-1) \equiv 0 \pmod n$, implying that either $x \equiv 1 \pmod n$ and/or $x \equiv -1 \bmod n$.

But why does it matter if $n$ is prime or not here?

For example $9^2 \equiv 1 \pmod {10}$, and $(9-1)(9+1) \equiv 0 \pmod {10}$ is true since $9+1 \equiv 0 \pmod{10}$

Isn't this congruence true regardless of what $n$ is, assuming we set $x^2 \equiv 1 \pmod{n}$? What exactly is the necessary condition for $n$ being prime and why isn't it true if $n$ is composite?

Answer 1

If we know that $a \cdot b \equiv 0 \pmod n$, we know that the $a \cdot b$ must be a multiple of $n$; in other words, the product $ab$ must contain (the prime factorization of) $n$. Now if $n$ is prime, the only way $ab$ will contain $n$ is if at least one of $a$ or $b$ contains $n$ in their prime factorizations. Therefore at least one of $a$ or $b$ has to be congruent to $0 \pmod n$.

---

If $n$ is composite ($n = pq$), then we could have $a = k_1 p$ and $b = k_2 q$. The product $ab = k_1 k_2pq$ is congruent to $0$ $\pmod n$, but as you can see, neither of $a$ nor $b$ are individually congruent to $0 \pmod n$.

The proprety we are discussing is called Euclid's Lemma.

Answer 2

It matters if $n$ is a prime or not. Take $n=8$, for example. The equation $x^2-1=0\pmod8$ has four solutions, $x=1, x=3,x=5$ and $x=7$. In general for any polynomial $f(x)$ of degree $d$ with integer coefficients the congruence equation $f(x)\equiv0\pmod p$ cannot have more than $d$ solution for primes $p$.