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?