Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod4$.

Question

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod 4$.

Would someone explain to me why exactly one of the four square roots of $x^4 \pmod {pq}$ is also a square?

This result was given without proof and I do not understand.

What I have tried: Edit: This boils down to proving that some $\exists$ $a: a^2 \cong x^4 \pmod {pq}$, $a$ is a quadratic residue $\pmod {pq}$

Since $p = q = 3 \pmod 4$, I know that the value of the Legendre symbol ($\frac{-1}{pq})$ is $-1$.

So, if the four candidates are $x,-x,y,-y$, one of $x,-x$ and one of $y,-y$ is not a quadratic residue, due to the multiplicity of the Legendre Symbol.

Without loss of generality, let's assume $x$ and $y$ are left as candidates. Without loss of generality, how can we prove $y$ is not a square/quadratic residue $\pmod {pq}$?

Answer 1

I work under the assumption that $x^4$ has to be replaced by $x^2$ in the formulation of the problem, otherwise $x^2$ is the required square root of $x^4$.

There are four distinct square roots of $1$ in $\Bbb{Z}_{n}$, where $n = p q$, say $1, -1, a, -a$. (Addendum Recall that we (can choose to) have $a \equiv 1 \pmod p$ and $a \equiv -1 \pmod{q}$.)

The four square roots of $x^2$ modulo $n$ are $x, -x, a x, -a x$. Now with the choice of $a$ as in the Addendum above, we have that the four $\left(\dfrac{p-1}{2}\right)$-th and $\left(\dfrac{q-1}{2}\right)$-th powers of these elements are $$ x^{(p-1)/2}, - x^{(p-1)/2}, x^{(p-1)/2}, - x^{(p-1)/2} \quad\text{modulo $p$} $$ and $$ x^{(q-1)/2}, - x^{(q-1)/2}, - x^{(q-1)/2}, x^{(q-1)/2} \quad\text{modulo $q$}. $$ This is because $\dfrac{p-1}{2}$ and $\dfrac{q-1}{2}$ are odd, so if $\epsilon \in \{ 1, -1, a, -a \}$, then $\epsilon \equiv \pm 1 \pmod{p}$ (see the Addendum above), so that $$ \epsilon^{{(p-1)}/{2}} \equiv \epsilon \pmod{p}, $$ and similarly for $q$.

Now recall that $$ x^{(p-1)/2} = \begin{cases} 1 & \text{if $x$ is a square modulo $p$,}\\ -1 & \text{if $x$ is not a square modulo $p$,} \end{cases} $$ and similarly for $q$.

Checking all four possibilities for the signs, we see that for exactly one of the elements $b$ among $x, -x, a x, -a x$ we have we have that both its $\left(\dfrac{p-1}{2}\right)$-th and $\left(\dfrac{q-1}{2}\right)$-th powers are $1$, so $b$ is a square modulo $p$ and $q$, so it is a square modulo $n = p q$.

Answer 2

We have equations $y^4 \equiv x^4 \pmod p $ if p|x then 0 is the soln. which is $0^2$

otherwise $(yx^{-1})^4 \equiv 1 \pmod p$.

As gcd(4,p-1)= 2 as($p \equiv 3 \pmod 4$),by fermat's little theorem it reduces to solve $(yx^{-1})^2 \equiv 1 \pmod p$ i.e. $y^2 \equiv x^2 \pmod p $ i.e. $y = (+1 or -1)x \pmod p$

Now it is easy to observe that either x or -x is a square mod p is a square. Because $p \equiv 3 \pmod 4 $ Let g be generator of $(\Bbb Z / p \Bbb Z)^*$ . Then $g^{(p-1)/2} = -1$ and (p-1)/2 is odd. Take i s.t. $g^i = x$, if i is even we are done. If i is odd $-x = (-1)*x = g^{i + (p-1)/2}$ is a square. Thus it is a square mod p.

Similarly either x or -x is a square mod q . And by chinese remainder thm we are done!