How do you find the squares mod 23?

Question

1.) Compute the squares modulo 23 as efficiently as possible.

2.) Show that $y^2 = 23x^2 + 7$ has no integer solutions.

This is a two part problem on my review for number theory and I am a bit lost. After going to my professor with this his hint was for part 2 saying to reduce it to mod 23. Having a really tough time with this problem any help is greatly appreciated.

Answer 1

The squares modulo $\;23\;$ are $\;0,1,4,9,16,2,13,3,18,12,8,6\;$ , so

$$y^2=23x^2+7=7\pmod{23}$$

and there's no element that squared modulo $\;23\;$ equals $\;7\pmod{23}\;$ .

Answer 2

Answering part 2 only. We immediately see that $-7\equiv16\pmod{23}$ is a quadratic residue, because it is a square. Because $23\equiv-1\pmod4$ we also know that $-1$ is not a QR mod $23$. As the Legendre symbol is a multiplicative character this means that $7$ is a quadratic non-residue.

---

An afterthought about part 1. We immediately see that $2\equiv5^2$ is quadratic residue. So are its powers $1,2,4,8,16,32\equiv9, 18, 36\equiv13,26\equiv3,6,12$. That's eleven residue classes, so we are done. Of course, the fact that $(11,23)$ is a Sophie Germain pair of primes makes finding a generator for the group of QRs easy.

Answer 3

METHOD $1$

Use that $5$ is a primitive root

$$7 \not \in \mathbb{U}=\left\{5^2, 5^4, 5^6, \dots, 5^{22} \right\} \equiv \left\{2, 2^2, 2^3, \dots, 2^{11} \right\}=\left\{2,4,8,16,9,18,13,3,6, 12, 1\right\}$$

METHOD $2$

$$(\frac{7}{23})=-(\frac{23}{7})=-(\frac{16}{7})=-1$$ by quadratic reciprocity.