# How do you find the squares mod 23?

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.

-
What does "efficiently" mean? For example, you only need to check all the integers modulo $\;23\;$ between $\;0\;$ and $\;11\;$ ... – Joanpemo Mar 12 at 22:04
Well, if you know quadratic reciprocity then it's quite fast. But even without that, brute force is quite efficient. – lulu Mar 12 at 22:04

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}\;$ .

-
Appreciate it, how did you calculate the squares of mod 23? – Nick Powers Mar 12 at 22:15
@NickPowers As I wrote in my comment: square by hand the elements $\;\mod{23}\;$ between $\;0\;$ and $\;11\;$ . Can you see why this is enough? – Joanpemo Mar 12 at 22:18
Shouldn't 8 squared be 18 not 19? – Nick Powers Mar 12 at 22:25
Just to confirm what I did was right. And yes I see why we only go u to 11, because after that it repeats the same numbers in reverse order. – Nick Powers Mar 12 at 22:25
@NickPowers Thank you, yes: a typo. Corrected. And yes, that's the reason as raising to an even power a number or its negative is the same. – Joanpemo Mar 12 at 22:30

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.

-
When $-1$ (and $2$) are QRs or QNRs comes up so often that it is second nature to look at those first. – Jyrki Lahtonen Mar 12 at 22:37

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.

-