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.

  • $\begingroup$ First minor observation: you can skip the case where k is a multiple of 4 (for strategy 2). $\endgroup$ – Mike Jan 16 '13 at 15:30

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.

  • 1
    $\begingroup$ I think you forgot $14+9=23$ and that explains why there are more solutions. In general, $$|(x,y)| \times |(a,b)| = \mbox{Number of total solution} $$ and one doesn't actually need to combine all the solutions to check for doubles since the CRT ensure unique solution for each pair. $\endgroup$ – LinAlgMan Jan 16 '13 at 16:54
  • $\begingroup$ @LinAlgMan: you are right. I got confused and thought I was working $\pmod 23$ at that point and could stop at $11^2$, but really needed to go up to $15^2$. I have fixed. That accounts for $64$ as there are four pairs and four choices of sign, so $2^4 \cdot 4=64$. $\endgroup$ – Ross Millikan Jan 16 '13 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.