How to determine whether a number can be written as a sum of two squares?
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?
Solution 1:
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$.