1
$\begingroup$

Suppose the $p$ is an odd prime not dividing $ab$. Prove that $z^2 \equiv ab$ mod $p$ is solvable if and only if both or neither of $x^2 \equiv b$ mod $p$ are solvable.

I have no idea how to prove this.

$\endgroup$
  • 1
    $\begingroup$ Well certainly if both $a$ and $b$ are perfect squares $\pmod{p}$, then so too will be their product. Write out precisely what that means and apply commutativity to make that direction come out. $\endgroup$ – Kaj Hansen Apr 14 '15 at 17:28
  • 1
    $\begingroup$ Let $\mathbb{Z}_p^* $ be the set of nonzero elements of $\mathbb{Z}/p\mathbb{Z}$. Did you know that $\mathbb{Z}_p^* $ is a cyclic group? Let $g$ be the generator of that group. What happens if you raise $g$ to an even power or odd power? $\endgroup$ – jkabrg Apr 14 '15 at 17:33
1
$\begingroup$

In other contexts, one might phrase this question as trying to prove that the product of two quadratic nonresidues is a quadratic residue. The "standard" way typically presented in elementary number theory texts (and suggested by user in the comments) is to first show that the nonzero elements mod $p$ have a generator (a primitive root) $g$. In this case, the squares are precisely those represented by even powers of $g$. Since the product of two odd powers of $g$ is an even power of $g$, that would prove your claim.

But we can go from first principles and use only basic algebra. Denote the nonzero elements mod $p$ by $(\mathbb{Z}/p\mathbb{Z})^\times$, and denote the squares by $S$. Then the key idea is that $S$ is a subgroup of $(\mathbb{Z}/p\mathbb{Z})^\times$.

We can check this directly. If $x \equiv a^2$ and $y \equiv b^2$, then $xy \equiv (ab)^2$. Similarly, $x^{-1} \equiv (a^{-1})^2$, and so $S$ is a subgroup.

We ask the fundamental question: how large is $S$? Since $1^2 = (-1)^2 = 1$, we can't hit every element. Consider the group homomorphism $\sigma: (\mathbb{Z}/p\mathbb{Z})^\times \longrightarrow (\mathbb{Z}/p\mathbb{Z})^\times$ given by $\sigma:x \mapsto x^2$. That is, consider the squaring map. More specifically, consider the kernel of $\sigma$.

We want to know when $\sigma (x) = 1$, or rather $x^2 \equiv 1 \pmod p$. This is equivalent to $p \mid x^2 - 1 = (x - 1)(x + 1)$, or rather $x \equiv \pm 1 \pmod p$. (We have used that $p$ is prime). So the size of the kernel is $2$.

Since very clearly $\sigma$ surjects onto $S$, we see that $S$ is an index $2$ subgroup of $(\mathbb{Z}/p\mathbb{Z})^\times$. An index $2$ subgroup is always normal, and so we can make sense of the quotient group $(\mathbb{Z}/p\mathbb{Z})^\times / S$.

This quotient group has $2$ elements. There is only one $2$ element group, and it's isomorphic to $\{1, -1\}$ under multiplication. Being $1$ in this quotient group corresponds to an element of $S$. Being $-1$ corresponds to being a non-square.

It is now clear that the product of two nonsquares, in the quotient group, acts like $-1 \cdot -1 = 1$, and is therefore a square.

More generally, the product of two squares is a square, the product of two nonsquares is a square, and the product of a square and a nonsquare is a nonsquare. It behaves (quite literally) like $-1$ and $1$ under multiplication. $\diamondsuit$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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