Solution to $x^2 \equiv 1$ (mod $pq$), $p,q \geq 3$ primes.

Question

Found the following piece online and got stuck:

Let $p,q \geq 3$ be different primes. Show that there is an integer $x$ such that $x^2 \equiv 1$ (mod pq) with $x$ neither congruent with $1$ or $−1$ (mod pq).

Would appreciate some help.

Answer 1

By Bezout we have $Ap+Bq=1$. Now consider $x=Bq-Ap$, modulo $p$ and $q$.

Answer 2

By the Chinese Remainder Theorem, there exists $x$ such that $x \equiv 1 \pmod{p}$ and $x \equiv -1 \pmod{q}$. Then $x^2 \equiv 1 \pmod{p}$ and $x^2 \equiv 1 \pmod{q}$, so again by (the uniqueness part of) the Chinese Remainder Theorem it follows that $x^2 \equiv 1 \pmod{pq}$. However, we cannot have $x \equiv 1 \pmod{pq}$, or this would imply $x \equiv 1 \pmod{q}$, so $1 \equiv -1 \pmod{q} \Rightarrow q \mid 2$ contradicting the assumption that $q \ge 3$. Similarly, from $p \ge 3$ we get $x \not\equiv -1 \pmod{pq}$.

Answer 3

I prefer somehow to have a "structural" explanation. By the CRT, we have an isomorphism of rings $\mathbf Z/pq\cong \mathbf Z/p \times \mathbf Z/q$. For $x \in \mathbf Z$, let us adopt the obvious notation $x_{pq}=(x_p , x_q)$ in the respective quotient rings. We must solve ${x_{pq}}^2=1_{pq}$ , or equivalently $(x_{pq}-1_{pq})(x_{pq}+1_{pq})=0_{pq}$, but we cannot conclude directly because $\mathbf Z/pq$ admits divisors of zero, i.e. this ring is not a domain. Working in $\mathbf Z/p \times \mathbf Z/q$ instead, we get immediately the necessary and sufficient condition $x_p=\pm 1_p$ and $x_q=\pm 1_q$ because $\mathbf Z/p$ and $\mathbf Z/q$ are fields. Moreover, $x_{pq}=1_{pq}$ iff $x_p=1_p$ and $x_q=1_q$. This means that, if $p$ and $q$ are odd, the non trivial solutions (viewed in $\mathbf Z/pq\cong \mathbf Z/p \times \mathbf Z/q$ ) are $(1_p , {-1}_q), ({-1}_p , 1_q)$ and $({-1}_p , {-1}_q)$ .