Sum of Squares

Consider equations of the form: $a^2 + b^2 = N$, $0 \le a \le b$, $a$, $b$ and $N$ integer.
For $N=65$ there are two solutions:
$a=1$, $b=8$ and $a=4$, $b=7$.
We call $S(N)$ the sum of the values of $a$ of all solutions of $a^2 + b^2 = N$, $0 \le a \le b$, $a$, $b$ and $N$ integer.
Thus $S(65) = 1 + 4 = 5$.
Find $\sum S(N)$, for all squarefree $N$ only divisible by primes of the form $4k+1$ with $4k+1 \lt 150$.

We start by identifying the primes that are of the form $4k+1$ and less than $150$. Those are: $5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149$. We have to consider all the squarefree numbers that can be made with these primes. A squarefree number is a number which is not divisible by the square of any prime. In this case, we simply need to consider all subsets of our set of primes.

For each number $N$ we have to calculate $S(N)$, the sum of the a-values for all solutions of $a^2 + b^2 = N$, $0 \le a \le b$, $a$, $b$ and $N$ integer.

The task can be done by the Gaussian integers method. Recall that if $N = a^2 + b^2$, than $N$ can be factored in the ring of Gaussian integers as $(a+bi)(a-bi)$. Therefore, we can quickly find pairs $(a,b)$ solving the equation $a^2 + b^2 = N$ by looking at the Gaussian factorization of $N$. We add the $a$-values (choosing $a \le b$), getting $S(N)$.

After calculating $S(N)$ for every relevant $N$, we must sum all these values up, giving us the $\sum S(N)$ we are looking for.

However, given the complexity of the problem, doing this by hand will be quite tedious. This kind of problem is well-suited to solve by a computer program. The exact solution can be obtained by writing a custom program that performs these computations.

More Answers: