Necessary and sufficient condition for prime I was reading Miller–Rabin primality test and there was a statement as:

$p$ is a prime iff $x^2 \cong 1\text{
 mod }p \implies x \cong \pm 1\text{ mod }p$ for all $x$.

I was able to do it from left to right (a simple proof indeed), but I couldn't do the converse. I tried the following:
$x^2 \cong 1\text{ mod }p \implies (x-1)(x+1)\cong 0\text{ mod }p \implies p \text{ divides }(x-1)(x+1)$. But I wasn't able to proceed further. Any help would be great. Thanks...
 A: When $x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is False
Assume that $p \not\in \{1,2,4,q^t,2q^t\}$ where $q$ is an odd prime and $t$ is a positive integer.
If $p$ is a power of $2$ greater than $4$, it is clear that $x=\frac{p}{2}-1$ shows the necessary since:
$$\bigg(\frac{p}{2}-1\bigg)^2 \equiv \frac{p^2}{4}-p+1 \equiv 1 \pmod{p}$$
Let $p$ not be a power of $2$. Clearly, we have some odd prime $q \mid p$. Let $t$ be the highest power of $q$ dividing $p$, i.e. $q^t \mid \mid p$. Now, let $p=k \cdot q^t$.
Since $p \not\in \{1,2,4,q^t,2q^t\}$ , we must have $k>2$. Also, since $q$ is an odd prime and $t$ is a positive integer, $q^t>2$.
We will show that there exists $x$ such that $x^2 \equiv 1 \pmod{p}$ and $x \not\equiv \pm 1 \pmod{p}$. We allow: $$q^t \mid (x+1) \implies x=q^tn-1$$
Now, we need $k \mid (x-1)$. This is the same as $k \mid (q^tn-2)$. However, we know from the fact that $\gcd(k,q^t)=1$ that:
$$q^tn \equiv 2 \pmod{k}$$
has a solution for $0<n<k$. Now, set $n$ such that this congruence is satisfied. It is clear that:
$$k \cdot q^t \mid (x-1)(x+1) \implies x^2 \equiv 1 \pmod{p}$$
If $x \equiv 1 \pmod{p}$, we need $q^t \mid (x+1) \implies q^t \mid 2$ which is clearly false as $q^t>2$.
Similarly, if $x \equiv -1 \pmod{p}$, we need $k \mid (x-1) \implies k \mid 2$ which is again false as $k>2$.
This shows that $x \not\equiv \pm 1 \pmod{p}$. This proves that for these values of $p$, $x^2 \equiv 1 \pmod {p}$ does not imply $x \equiv \pm 1 \pmod{p}$.
When $x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is True
Clearly, this is true for $p \in \{1,2,4\}$. We will show that it is true for $p=q^t$ and $p=2q^t$. Let $x^2 \equiv 1 \pmod{q^t}$. This shows that:
$$q^t \mid (x-1)(x+1)$$
Since $q \nmid 2$, $q$ cannot divide both factors. This means that $q^t$ has to divide one of the factors completely.
$$q^t \mid (x \pm 1) \implies x \equiv \pm 1 \pmod{q^t}$$
When $p=2q^t$, since $x^2 \equiv 1 \pmod{p}$, we will additionally have $x$ to be odd as $p$ is even. This gives an additional condition $x \equiv 1 \pmod{2}$ showing that $x \equiv \pm 1 \pmod{2q^t}$.
Summary

*

*$x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is True for $p \in \{1,2,4,q^t,2q^t\}$ where $q$ is an odd prime and $t$ is a positive integer.

*$x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is False otherwise.

Counterexamples
The counterexamples are when for $p$ not prime:
$$x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$$
From above, this is the set $\{1,4,q^a,2q^b\}$ where $q$ is an odd prime, $a$ and $b$ are positive integers, and $a>1$. Note that $2$ and $q$ are removed as they are prime.
