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

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}$?

-
It'll be helpful if you give the context in which you found the problem and what you tried so that people can give you better answers – Phani Raj May 13 '13 at 8:06
Are you sure the formulation is correct as stated? The square $x^2$ is one the square roots of $x^4$, as $(x^2)^2 = x^4$. – Andreas Caranti May 13 '13 at 8:31
It is one of the square roots of $x^4 \pmod {pq}$. There are four. and only one of those is of the form $a^2$ (down to congruence $\pmod {pq}$. – Zéychin May 13 '13 at 8:35
I dare guess that you meant to say that one of the roots (=solutions) $x$ of $x^4\equiv a\pmod{pq}$ is also a square itself, i.e. $x=y^2$ for some $y$. At least that is how I interpreted the question when composing my answer. – Jyrki Lahtonen May 13 '13 at 8:39
I meant square root. For example, Let $x=1; x^4 = 1$. Then $-1$ is not a square $\pmod {pq}$, but is a square root of $x^4$. – Zéychin May 13 '13 at 8:45

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$.

-
Yes, we are solving the same problem. I am having trouble following how $(ax)^\frac{(p-1)}{2} = x^\frac{p-1}{2}$. I understand the calculations of the first two powers. I just don't understand how you are finding the signed-ness of the third and fourth powers. – Zéychin May 13 '13 at 9:10
@Zéychin, I have expanded the argument, see in particular the Addendum. – Andreas Caranti May 13 '13 at 9:26
Great. The addendum clarified things for me. It was simple, but I was tired and that really helped me. Thank you very much! – Zéychin May 13 '13 at 14:01
@Zéychin, you're welcome! – Andreas Caranti May 13 '13 at 14:06

Let us consider this one prime factor at a time (obviously planning to use the Chinese Remainder Theorem in the end).

We are given a number $a$ such that $x^4\equiv a\pmod{pq}$. So we also have that $x^4\equiv a\pmod{p}$. I claim that $x$ can be chosen in such a way that $x\equiv y^2\pmod p$ for some integer $y$. If $p\mid a$, then $p\mid x$, so $y=0, x=0$ works. Otherwise (the residue class of) $a$ is an element of the multiplicative group $G=\mathbb{Z}_p^*$ of residue classes coprime to $p$.

The group $G$ is cyclic of order $p-1$, let $g$ be a generator. We can take advantage of this as follows. From the given fact, $p\equiv3\pmod4$, it follows that $\gcd(4,p-1)=\gcd(8,p-1)=2$. Consider the two homomorphism $f:z\mapsto z^4$ and $g:z\mapsto z^8$ from the group $G$ to itself. The basic properties of cyclic groups tell us that the kernel of $f$ (resp. $g$) consists of elements of order dividing $4$ (resp. $8$). The above gcd-property implies that the kernels of these homomorphisms are then equal, consisting of element of orders dividing $2$. Therefore the kernels of the two homomorphisms are both equal to the cyclic subgroup of order two. The "freshman theorem" ($Im(f)\cong G/\ker f$) then tells us that the images of both $f$ and $g$ are of index two. But a cyclic group has only a single subgroup of each possible index, so the images of $f$ and $g$ must be the same subgroup.

Ok, so $a=x^4=f(x)$ is in the image of $f$. By the above result, $a$ is then also in the image of $g$. So there exists an integer $y_1$ such that $a\equiv g(y_1)=y_1^8\pmod p$. Repeating this argument modulo $q$ instead of modulo $p$ we find another integer $y_2$ such that $y_2^8\equiv a\pmod q$. By CRT, there exist an integer $y$ such that $y\equiv y_1\pmod p$ and $y\equiv y_2\pmod q$. Then $y^8\equiv y_1^8\equiv a\pmod p$ as well as $y^8\equiv a\pmod q$, so $$y^8\equiv a\pmod{pq}.$$ Therefore $x=y^2$ is a solution of $x^4\equiv a\pmod{pq}$ that also happens to be a quadratic residue.

-
If you are uncomfortable with the use of group homomorphisms, you can replace the third paragraph with the following argument. If $x$ is a solution of $x^4\equiv a\pmod p$, then $-x$ is another. As $p\equiv 3\pmod4$, we know that $-1$ is a quadratic non-residue. Therefore exactly one of $\pm x$ is a quadratic residue modulo $p$. Therefore $\pm x\equiv y_1^2\pmod p$ has a solution $y_1$ for that choice of the sign. Similarly find $y_2$, and then combine them to a solution modulo $pq$ as above. – Jyrki Lahtonen May 13 '13 at 8:36
So you can replace using endomorphisms of a cyclic group by using the theory of quadratic residues instead. I do not know which approach is a better fit to your background, so I include both. – Jyrki Lahtonen May 13 '13 at 8:37
Observe that you can keep going, because modulo $p$ (and $q$) all the squares are fourth powers, eighth powers, sixteenth powers et cetera. – Jyrki Lahtonen May 13 '13 at 8:45

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!

-