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}.$$
 A: 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$.
A: 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$. 
A: 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? 
