elementary number theory - If $ab equiv r pmod{p}$, and $x^2 equiv a pmod{p}$ then $y^2 equiv b pmod{p}$ for which condition of $r$?

For the special case $ab \equiv 1 \pmod{p}$, I already got very clear explanation from Arturo Magidin and Quanta in this thread Prove that if $ab \equiv 1 \pmod{p}$ and $a$ is quadratic residue mod $p$, then so is $b$

Now if $ab \equiv r \pmod{p}$, what condition need to be hold in order for this to be true, i.e If $a$ is quadratic residue modulo $p$, then $b$ is also quadratic residue modulo $p$.
My attempt was, I made a concrete example to observe the value of $r$, says $p = 7$. The results are: 1, 4, 5
$$1^2 \equiv 1 \pmod{7}$$

$$2^2 \equiv 4 \pmod{7}$$
$$3^2 \equiv 2 \pmod{7}$$
$$4^2 \equiv 1 \pmod{7}$$
$$5^2 \equiv 4 \pmod{7}$$
$$6^2 \equiv 1 \pmod{7}$$

So $r$ could be $1$, $2$, $4$, since $4.4 \equiv 1 \pmod{7}$ and $4.2 \equiv 1 \pmod{7}$. From these results, I saw that $r$ was also quadratic residue modulo $p$.
Another idea that I tried is adapting the proof from the mentioning thread above:
If $ab \equiv r \pmod{p}$, then
$$aa^{-1}b \equiv ra^{-1} \pmod{p} \Leftrightarrow b \equiv ra^{-1} \pmod{p}$$

$$bb^{-1}a \equiv rb^{-1} \pmod{p} \Leftrightarrow a \equiv rb^{-1} \pmod{p}$$

Then I tried to use the fact that $x^2 \equiv a \pmod{p}$, and $a \equiv rb^{-1} \pmod{p}$ to come with $x^2 \equiv rb^{-1} \pmod{p}$. But I could not find a way to express this in term of $y^2 \equiv b \pmod{p}$. Furthermore, I don't know if this algebraic manipulation could solve the condition for $r$ or not. Any idea? A hint would be greatly appreciated.

Thank you

Answer

The following three facts are relevant.

• If $a$ and $b$ are squares then $r$ is a square.





• If $a$ and $b$ are not squares then $r$ is a square.




• If one of $a,b$ is a square and the other is not then $r$ is not a square.

It's simple to prove the first one: Let $a = x^2$, $b = y^2$ so that $r = ab = (xy)^2$.

As for the next two I will give a "hi-tech" proof (See Martins comment for a direct proof).

Modular arithmetic $\mathbb{Z}/p\mathbb{Z}$ is a ring, but the group of units $(\mathbb{Z}/p\mathbb{Z})^\times$ is a group: It's the multiplicative part of the ring. The only non-unit is $0$ so as a set it's $\{1,2,\cdots,p-1\}$.

This group is cyclic (a very fundamental and strong theorem, see here for some discussion on it) and we can use this to prove the theorems: Let $g$ generate the group, so that every element is of the form $g^k$ for some $0 < k < p-1$,

• First note that $a$ is a square iff $a = g^{2k}$. (Easy to prove).

Let $a = g^u$, $b = g^v$ so $r = ab = g^{u+v}$. All three facts are an easy deduction from this. You can prove them now but I would like to define some good notation.

We can introduce the Legendre symbol now: Define a map $\left(\tfrac{-}{p}\right)$ that takes $g$ to $-1$ and extend it to the whole group: It's a group homomorphism from the units group $\mathbb{Z}/p\mathbb{Z}$ into $\{1,-1\}$. It's $1$ exactly when the number is a square and $0$ otherwise.

So now we have:

• If $a$ and $b$ are squares then $r$ is a square because $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = 1 \cdot 1 = 1$.




• If $a$ and $b$ are not squares then $r$ is a square because $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = -1 \cdot -1 = 1$.




• If one of $a,b$ is a square and the other is not then $r$ is not a square because $\left(\tfrac{r}{p}\right) = \left(\tfrac{ab}{p}\right) = \left(\tfrac{a}{p}\right)\left(\tfrac{b}{p}\right) = 1 \cdot -1 = -1$.