Sum of two squares modulo

Question

In the following all variables are non-negative integers.

It is well known (Fermat) that a number $a$ is a sum of two squares $a = x^2 + y^2$ if and only if the prime factors of $a$ of the form $p = 4k+3$ occurs to an even power. Example: $$7^2 \times 5 = 245 = 7^2 + 14^2 \ .$$

I want to count how many solutions there are to the equation $$ x^2 + y^2 \equiv 23 \pmod {93} $$ (it is enough to take $x$ and $y$ from the set $A = \{ 0,1,2,...,92 \}$).

In this case Fermat's Theorem does not hold as it is. For example, we have $23=4 \times 5 + 3$ but $23 + 93 = 116 = 10^2 + 4^2$ is indeed a sum of two squares modulo 93. This also shows that this equation has at least one solution.

There are several strategies to this question:

1. Check all the possible values of $(x,y) \in A \times A$ explicitly.

2. Check all the possible values of $\{ b = 23 + 93k \mid k \in \mathbb{Z} \}$ such that $b$ not exceeding $2 \times 93^2$, and see if they are decomposable to sum of two squares.

Both options require a computer program to do all the calculations in a reasonable time. I want a way based on theory with calculations which can be done by hand on the blackboard.

Answer 1

First, you can factor $93$ and solve $x^2+y^2=2 \pmod 3$ and $a^2+b^2=23 \pmod {31}$, then combine the results using the Chinese Remainder theorem. The first is easy-we must have $x,y=\pm 1 \pmod 3$. For the second, you only have to try $0$ through $11$, as $a^2=(-a)^2$ and the first few you know. The squares $\pmod {31}$ are $0,1,4,9,16,25,5,18,2,19,7,28,20,14,10,8$. Now look through this list for pairs that sum to $23$ or $64$. It is not too hard to see that the solutions are $4+19, 16+7, 5+18, 9+14$. So we can have $a=\pm 2, b=\pm 9 \pmod {31}$, giving four solutions that have to be combined with being $1 \pmod 3$ by CRT. $a=2, b=9$ gives $(2,40), (64,40), (2,71), (64,71)$, which you can probably do by inspection-just add $31$'s until you don't have a multiple of $3$. The three other choices of sign will each give four more. The three other choices for sums will each give sixteen more answers, so there are $64$ in all. I think this is within the range of blackboard work.