2
$\begingroup$

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?)
$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ian Mar 24 '15 at 17:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Nathanson Mar 24 '15 at 17:25
  • 2
    $\begingroup$ 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$. $\endgroup$ – Ian Mar 24 '15 at 17:27
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Prasun Biswas Mar 24 '15 at 17:43
  • $\begingroup$ 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}$ ? $\endgroup$ – Richard Mar 25 '15 at 2:57
3
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Richard Mar 25 '15 at 13:21
  • $\begingroup$ mathworld.wolfram.com/SumofSquaresFunction.html $\endgroup$ – Yves Daoust Mar 25 '15 at 13:40
2
$\begingroup$

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.$$

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – Richard Mar 25 '15 at 2:47
  • $\begingroup$ 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}$ ? $\endgroup$ – Richard Mar 25 '15 at 2:56
0
$\begingroup$

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$

$\endgroup$

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.