# A problem I didn't know since high school algebra

Determine all positive integers which can be written as a sum of two squares of integers.

This is a problem I saw when I was in high school...

1. sum of two squares of integers can be (4k, 4k+1, 4k+2, but no 4k+3?)
• A partial solution to your first question is the collection of squares which can be written as a sum of two squares of integers. These are the Pythagorean triples, and can be generated by the formula $k^2 (m^2+n^2)^2$ for positive integers $k,m,n$. – Ian Mar 24 '15 at 17:23
• They are numbers in which the prime factors of the form $4k+3$ appear to even powers. Begin reading from here and here. To pass from the solution for primes to all the numbers use Brahmagupta's identity. – Nathanson Mar 24 '15 at 17:25
• As for your high school problem, notice that $(4k)^2=16k^2=4n$, $(4k+1)^2=16k^2+8k+1=4n+1$,$(4k+2)^2=16k^2+16k+4=4n$,$(4k+3)^2=16k^2+24k+9=4n+1$. (The values of $n$ are different.) So a square is never of the form $4k+3$. So a square can only have remainder either $0$ or $1$ when divided by $4$. When you add the squares, the remainders add, so the remainders can only be $0$,$1$, or $2$. – Ian Mar 24 '15 at 17:27
• Concisely, consider $x$ and $y$ as two arbitrary integers. We can have $x,y\equiv \{0,1,2,3\}\pmod{4}\implies x^2,y^2\equiv \{0,1\}\pmod{4}\implies x^2+y^2\equiv \{0,1,2\}\pmod{4}$ – Prasun Biswas Mar 24 '15 at 17:43
• A big thanks to @Nathanson common. One more question, how to check the integer of the form 4n, and 4n+2 can be written as $a^{2}+b^{2}$ ? – Richard Mar 25 '15 at 2:57

The square of an even number is a multiple of $4$ (i.e. $4k^2)$, and that of an odd number is a multiple of $4$ plus $1$ (i.e. $4(k^2+k)+1$). So the sum of two squares is a multiple of $4$, plus $0$, $1$ or $2$.

Anyway, not all numbers for the form $4k$, $4k+1$ or $4k+2$ are sums of two squares (take $12$, $21$ and $6$), so this does not really answer the question.

A better criterion was given by Euler: an integer is the sum of two squares ($0$ allowed) iff its prime factors of the form $(4k+3)$ have an even multiplicity.

\begin{align} 2&= 2\ \\ 3&= \color{red}{ 3\ } \\ 4&= 2^{2}\ \\ 5&= 5\ \\ 6&= 2\ \cdot \color{red}{ 3\ } \\ 7&= \color{red}{ 7\ } \\ 8&= 2^{3}\ \\ 9&= \color{green}{ 3^{2}\ } \\ 10&= 2\ \cdot 5\ \\ 11&= \color{red}{ 11\ } \\ 12&= 2^{2}\ \cdot \color{red}{ 3\ } \\ 13&= 13\ \\ 14&= 2\ \cdot \color{red}{ 7\ } \\ 15&= \color{red}{ 3\ } \cdot 5\ \\ 16&= 2^{4}\ \\ 17&= 17\ \\ 18&= 2\ \cdot \color{green}{ 3^{2}\ } \\ 19&= \color{red}{ 19\ } \\ 20&= 2^{2}\ \cdot 5\ \\ 21&= \color{red}{ 3\ } \cdot \color{red}{ 7\ } \\ 22&= 2\ \cdot \color{red}{ 11\ } \\ 23&= \color{red}{ 23\ } \\ 24&= 2^{3}\ \cdot \color{red}{ 3\ } \\ 25&= 5^{2}\ \\ 26&= 2\ \cdot 13\ \\ 27&= \color{red}{ 3^{3}\ } \\ 28&= 2^{2}\ \cdot \color{red}{ 7\ } \\ 29&= 29\ \\ 30&= 2\ \cdot \color{red}{ 3\ } \cdot 5\ \\ 31&= \color{red}{ 31\ } \\ 32&= 2^{5}\ \\ 33&= \color{red}{ 3\ } \cdot \color{red}{ 11\ } \\ 34&= 2\ \cdot 17\ \\ 35&= 5\ \cdot \color{red}{ 7\ } \\ 36&= 2^{2}\ \cdot \color{green}{ 3^{2}\ } \\ 37&= 37\ \\ 38&= 2\ \cdot \color{red}{ 19\ } \\ 39&= \color{red}{ 3\ } \cdot 13\ \\ 40&= 2^{3}\ \cdot 5\ \\ 41&= 41\ \\ 42&= 2\ \cdot \color{red}{ 3\ } \cdot \color{red}{ 7\ } \\ 43&= \color{red}{ 43\ } \\ 44&= 2^{2}\ \cdot \color{red}{ 11\ } \\ 45&= \color{green}{ 3^{2}\ } \cdot 5\ \\ 46&= 2\ \cdot \color{red}{ 23\ } \\ 47&= \color{red}{ 47\ } \\ 48&= 2^{4}\ \cdot \color{red}{ 3\ } \\ 49&= \color{green}{ 7^{2}\ } \\ 50&= 2\ \cdot 5^{2}\ \\ 51&= \color{red}{ 3\ } \cdot 17\ \\ 52&= 2^{2}\ \cdot 13\ \\ 53&= 53\ \\ 54&= 2\ \cdot \color{red}{ 3^{3}\ } \\ 55&= 5\ \cdot \color{red}{ 11\ } \\ 56&= 2^{3}\ \cdot \color{red}{ 7\ } \\ 57&= \color{red}{ 3\ } \cdot \color{red}{ 19\ } \\ 58&= 2\ \cdot 29\ \\ 59&= \color{red}{ 59\ } \\ 60&= 2^{2}\ \cdot \color{red}{ 3\ } \cdot 5\ \\ 61&= 61\ \\ 62&= 2\ \cdot \color{red}{ 31\ } \\ 63&= \color{green}{ 3^{2}\ } \cdot \color{red}{ 7\ } \\ 64&= 2^{6}\ \\ 65&= 5\ \cdot 13\ \\ 66&= 2\ \cdot \color{red}{ 3\ } \cdot \color{red}{ 11\ } \\ 67&= \color{red}{ 67\ } \\ 68&= 2^{2}\ \cdot 17\ \\ 69&= \color{red}{ 3\ } \cdot \color{red}{ 23\ } \\ 70&= 2\ \cdot 5\ \cdot \color{red}{ 7\ } \\ 71&= \color{red}{ 71\ } \\ 72&= 2^{3}\ \cdot \color{green}{ 3^{2}\ } \\ 73&= 73\ \\ 74&= 2\ \cdot 37\ \\ 75&= \color{red}{ 3\ } \cdot 5^{2}\ \\ 76&= 2^{2}\ \cdot \color{red}{ 19\ } \\ 77&= \color{red}{ 7\ } \cdot \color{red}{ 11\ } \\ 78&= 2\ \cdot \color{red}{ 3\ } \cdot 13\ \\ 79&= \color{red}{ 79\ } \\ 80&= 2^{4}\ \cdot 5\ \\ 81&= \color{green}{ 3^{4}\ } \\ 82&= 2\ \cdot 41\ \\ 83&= \color{red}{ 83\ } \\ 84&= 2^{2}\ \cdot \color{red}{ 3\ } \cdot \color{red}{ 7\ } \\ 85&= 5\ \cdot 17\ \\ 86&= 2\ \cdot \color{red}{ 43\ } \\ 87&= \color{red}{ 3\ } \cdot 29\ \\ 88&= 2^{3}\ \cdot \color{red}{ 11\ } \\ 89&= 89\ \\ 90&= 2\ \cdot \color{green}{ 3^{2}\ } \cdot 5\ \\ 91&= \color{red}{ 7\ } \cdot 13\ \\ 92&= 2^{2}\ \cdot \color{red}{ 23\ } \\ 93&= \color{red}{ 3\ } \cdot \color{red}{ 31\ } \\ 94&= 2\ \cdot \color{red}{ 47\ } \\ 95&= 5\ \cdot \color{red}{ 19\ } \\ 96&= 2^{5}\ \cdot \color{red}{ 3\ } \\ 97&= 97\ \\ 98&= 2\ \cdot \color{green}{ 7^{2}\ } \\ 99&= \color{green}{ 3^{2}\ } \cdot \color{red}{ 11\ } \\ 100&= 2^{2}\ \cdot 5^{2}\ \\ \end{align}

• May I ask, where does "A better criterion was given by Euler: an integer is the sum of two squares (0 allowed) iff its prime factors of the form (4k+3) have an even multiplicity." from? And how to proof this criterion? – Richard Mar 25 '15 at 13:21
• mathworld.wolfram.com/SumofSquaresFunction.html – Yves Daoust Mar 25 '15 at 13:40

Every integer $n$ can be expressed as $n=4k+r$ for $r=0,1,2,3$. $r$ is called the remainder after division by 4. Now $n^2 = (4k+r)^2 = 4^2k^2 + 8kr + r^2$.

If $r = 0$ then $r^2=0$. So $n^2=4k'$ for some $k'$.

If $r=1$ then $r^2=1$. So $n^2=4k'+1$ for some $k'$.

If $r=2$ then $r^2=4$. So $n^2=4k'$ for some $k'$.

If $r=3$ then $r^2 = 9 = 2\cdot 4 + 1$. So $n^2 = 4k'+1$ for some $k'$.

Thus the square of every integer can be expressed as $n^2 = 4k + r$ where $r=0$ or $r=1$.

Thus the sum of two squares can have the following remainders after division by 4:

$$1+1=2$$ $$1+0=1$$ $$0+0=0$$

Note that we cannot have a remainder of 3, since this has exhausted all the possibilities.

A neat thing that you can show with a bit of imaginary numbers is that the product of two numbers that are a sum of squares is again a sum of squares.

$$(n^2+m^2)(a^2+b^2)$$ $$= (n+im)(n-im)(a+ib)(a-ib)$$ $$= (an-bm+i(nb+ma))(an-bm-i(nb+ma))$$ $$=(an-bm)^2+(nb+ma)^2$$

Thus if we take $10=3^2+1$ and $8=2^2+2^2$ we can write $80$ as the sum of two squares:

$$80 = (6-2)^2+(6+2)^2 = 4^2 + 8^2.$$

• So, if I want to find out all positive integers can be written as $a^{2}+b^{2}$. First, they must be of the form $4n, 4n+1, 4n+2$. Second, say 1,2,4,5,8,9,10 are the positive integers satisfies $a^{2}+b^{2}$, then, how do I know if there is a large prime of the form 4n+1, which may be written as $a^{2}+b^{2}$? – Richard Mar 25 '15 at 2:47
• Okay, I find the answer through @Nathanson common. One more question, how to check the integer of the form 4n, and 4n+2 can be written as $a^{2}+b^{2}$ ? – Richard Mar 25 '15 at 2:56

For $a,b$ in $a^2+b^2$, consider three cases:

1) Both $a,b$ are even. Then $a^2+b^2=4k^2+4k'^2$ which is of the form $4k$.

2) Both $a,b$ are odd. Then $a^2+b^2=8k+1+8k'+1=4(2k+2k')+2$ which is of the form $4k+2$.

3) $a,b$ have the deifferent parity. WLOG suppose that a is odd and b is even. Then $a^2+b^2=8k+1+4k'=4(2k+k')+1$ which is of the form $4k+1$