Sum of two squares theorem

Question

I am working on the problem: I need to quickly check if positive number $n$ can be expressed as $n^2=a^2+b^2$. I found this theorem: https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem

But it seems I am missing something. For example number $4$ falls under theorem condition: its prime decomposition doesn't have any prime $p\equiv 3{\pmod {4}}$. But $4$ cannot be expressed as sum of 2 squares.

Answer 1

In the theorem $a,b$ have to be integers and don't have to be nonzero. So in your example: $4=2^2+0^2$.

So the theorem doesn't really help in your case. $n^2=n^2+0^2$ but that doesn't help you much, since I assume that you have additional assumptions on $a,b$, like for example that they should both be nonzero.

Answer 2

The theorem is not at all useless. Note that if $n = x^2 + y^2$, $n^2 = (x^2-y^2)^2 + (2xy)^2$. Thus if $n$ is the sum of two squares, neither $0$ and not both equal, then $n^2$ is the sum of two nonzero squares.

Answer 3

Too big for a comment

The wiki presentation is wrong on at least one point. It says,

"The prime decomposition of the number $3430$ is $2 \cdot 5 \cdot 7^3$. This time, the exponent of $7$ in the decomposition is $3$, an odd number. So $3430$ cannot be written as the sum of two squares."

However $\qquad (2058^2+2744^2=3430^2)\qquad$ because $\qquad(2058,2744,3430)=686\times (3,4,5)$

To find if some square can be the sum of two squares, we begin with Euclid's formula shown here as

$$ \quad A=m^2-k^2,\quad B=2mk,\quad C=m^2+k^2\quad$$

We solve the C-function for $k$ and try a range of m-values to see which yield integers. Here is an example

\begin{equation} C=m^2+k^2\implies k=\sqrt{C-m^2}\qquad\text{for}\qquad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le m \le \lfloor\sqrt{C-1}\rfloor \end{equation} The lower limit ensures $m>k$ and the upper limit ensures $k\in\mathbb{N}$.

$$C=65\implies \bigg\lfloor\frac{ 1+\sqrt{130-1}}{2}\bigg\rfloor=6 \le m \le \lfloor\sqrt{65-1}\rfloor=8\quad\land \quad m\in\{7,8\}\Rightarrow k\in\{4,1\}\\$$ $$F(7,4)=(33,56,65)\qquad \qquad F(8,1)=(63,16,65) $$

This "formula" will not find $3430$ directly but, after factoring $3430$ we find that it is $686\cdot 5$ and this formula will find a triple for $C=5$. Multiplying each term by $686$ then yields $\quad (2058,2744,3430)$.