[Math] How to determine whether a number can be written as a sum of two squares

elementary-number-theory

I know the following theorems:

  • A number can be represented as a sum of two squares precisely when $N$ is of the form $n^2 \prod p_i$ where each $p_i$ is a prime congruent to 1 mod 4
  • If the equation $a^2 + 1 \equiv a (\text {mod} p)$ is solvable for some $a$, then $p$ can be represented as a sum of two squares.
  • A positive integer $n$ is the sum of two squares iff each prime factor $p$ of $n$ such that $ p \equiv 3 (\text{mod} 4)$ occurs to an even power in the prime factorization of $n$

My problem is often which one to use and exactly how to use it.

Here is an example of a question:

Determine whether the following integers can be written as the sum of two squares.
a) 363
b) 700
c) 34300
d) 325

For example, I figures 363 can not be written as a sum of two squares as it is of the form $4k +3$ where $k = 90$

For 700, which is not in the above stated form, I found $ 700 =2^2 \cdot 5^2 \cdot 7$ and 7 is the only factor $ p \equiv 3 mod 4$ and it is definitely not to an even power. Does this mean I'm done showing it is not the sum of two squares?

c) $34300 = 7^3 \cdot 5^2 \cdot 2^2$; again the power of 7 is not even.

d) Then I have $325 = 13 \cdot 5^2$ which has no prime factors congruent to 3 modulo 4. BUT $325 = 5^2(13)$ where $13 \equiv 1 mod 4$ and 5 is the $n$ mentioned in the first theorem. Is this enough to conclude that 325 is a sum of two squares?

Best Answer

A postive integer $n$ is representable as the sum of two squares, $n=x^2+y^2$ if and only if every prime divisor $p\equiv 3$ mod $4$ of $n$ occurs with even exponent. This is good enough to solve your questions.

a) $n=363=3\cdot 11^2$ is not the sum of two squares, since $3$ is a prime divisor $p\equiv 3$ mod $4$ occuring not with even multiplicity.

b) $n=700=2^2\cdot 5^2\cdot 7$ is not the sum of two squares. Take $p=7$.

c) $n=34300=2^2\cdot 5^2\cdot 7^3$ is not the sum of two squares. Take $p=7$.

d) $n=325=5^2\cdot 13$ is a sum of two squares, because every prime divisor $p\equiv 3$ mod $4$ occurs with even multiplicity - because $0$ is even. Of course, it is straightforward to see that, say, $325=10^2+15^2$.

Related Question