Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 1 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.