# Quadratic Congruence and Sum of Two Squares

How would one go about showing how many solutions the following congruence has? $$x^2 + y^2 \equiv 23 \pmod{93}.$$

-
You mean other than trying all values for x and y between 0 and 92, which would take a computer much less than a second to do? –  Alex B. Nov 26 '10 at 18:12

This is a start:

You would like to know for which y it holds that 23 - y^2 is a square modulo 93. As 93 is 31*3, you can find these y by finding the squares of the form 23 - y^2 modulo 3 and modulo 31. Can you go on from there?

-
Okay, so the possible solutions for y would only be +-1, +-2, +-3, and +-4? Because if they were any larger, 23-y^2 would result in a negative integer, which cannot happen since we are showing that this integer is a square. Then from there, I would just work out the congruences for each modulo to figure how many solutions there are. Would I total the number of solutions from modulo 3 and modulo 31? –  Katherine Nov 26 '10 at 18:58
...1, 2, 3, and 4 all work modulo 3. However, all solutions except for 1^2 work for modulo 31. Does this sound right? (23- 1^2 = 22 mod 31, which is not a square modulo 31) –  Katherine Nov 26 '10 at 19:12
@Katherine: since you are working in congruences, it simple does not matter whether $23-y^2$ is negative or not: you can always adjust by adding $93$ to the result, and still get the same number modulo $93$. –  Arturo Magidin Nov 26 '10 at 19:15

If you are working modulo a prime $p$, then you can obtain the result using the Legendre symbol or by simple trial and error if it is small. For instance, working modulo $3$, as CJost suggests, you are trying to solve $x^2 + y^2 \equiv 23 \equiv 2 \pmod{3}$. then you want to solve $x^2 \equiv 2-y^2\pmod{3}$. Since $y^2$ can only be congruent to $0$ or to $1$ modulo $3$, you only have solutions when $x^2\equiv y^2\equiv 1\pmod{3}$. That gives you four solutions modulo $3$: $(1,1)$, $(1,-1)$, $(-1,1)$, and $(-1,-1)$.

You need to do something similar for $31$: for each possibly value of $y^2$, decide if $23-y^2$ is a square modulo $31$; if it is, that gives you two possible values for $x$ and two possible values for $y$ (unless one of the two needs to be $0$ modulo $23$). But remember that you are working modulo $31$; for example, with $y=5$, there is no problem with the fact that $23-y^2 = -2$, because you are trying to solve $x^2\equiv -2\pmod{31}$, and this is the same as $x^2\equiv 29 \pmod{31}$; the negative number is not a problem. And of course, to decide if $x^2\equiv 29\pmod{31}$ has a solution, you can use the Legendre symbol and quadratic reciprocity to compute it.

Added: As it happens, $23$ is not a square modulo $31$, so any solutions to $x^2+y^2\equiv 23\pmod{31}$ will necessarily have both $x$ and $y$ not congruent to zero modulo $31$; so you don't need to worry about that when you are counting solutions.

Now, suppose you find a solution $x=a$ and $y=b$ modulo $31$. How do you get solutions modulo $93$? You take one solution modulo $3$, say $(1,1)$, and the solution modulo $31$, say $(a,b)$, and you use the Chinese Remainder Theorem: you can find an integer $x$ such that $x\equiv 1 \pmod{3}$ and $x\equiv a\pmod{31}$; then find an integer $y$ such that $y\equiv 1\pmod{3}$ and $y\equiv b\pmod{31}$. Then the pair $(x,y)$ will be a solution modulo $93$ that corresponds to the solution $(1,1)$ modulo $3$ and the solution $(a,b)$ modulo $31$. So each choice of a solution modulo $3$ and a solution modulo $31$ will give you a solution modulo $93$.

-

Let $$S=\sum_{x=0}^{92}\sum_{y=0}^{92}\sum_{t=0}^{92}e^{2\pi i(x^2+y^2-23)t/93}$$ For $x,y$ such that $x^2+y^2\not\equiv23\pmod{93}$, the sum on $t$ is zero; for $x,y$ such that $x^2+y^2\equiv23\pmod{93}$, the sum on $t$ is 93. So $S$ is $93$ times the number of solutions of the congruence.

Now interchange order of summation: $$S=\sum_{t=0}^{92}\sum_{x=0}^{92}\sum_{y=0}^{92}e^{2\pi i(x^2+y^2-23)t/93}$$ The terms with $t=0$ contribute $93^2$, so $$S=93^2+\sum_{t=1}^{92}e^{2\pi i(-23)t/93}\left(\sum_{x=0}^{92}e^{2\pi ix^2t/93}\right)^2$$

Now the inner sum is a quadratic Gauss sum and from the link we get $\left(\sum_{x=0}^{92}e^{2\pi ix^2t/93}\right)^2$ is $93$ if $\gcd(t,93)=1$; it's $-31(3)^2$ if $\gcd(t,93)=3$; and it's $-3(31)^2$ if $\gcd(t,93)=31$. So $$S=93^2+93\sum_{(t,93)=1}e^{2\pi i(-23)t/93}-31(3)^2\sum_{(t,93)=3}e^{2\pi i(-23)t/93}-3(31)^2\sum_{(t,93)=31}e^{2\pi i(-23)t/93}$$. The sums are seen to be $1,-1,-1$, respectively, so $S=93^2+93+93\times3+93\times31$.

So, the number of solutions of the congruence should be $93+1+3+31=128$.

-