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?

  • $\begingroup$ There is a generic formula for Pythagorean triples; is this what you are looking for? $\endgroup$ – user99680 May 9 '14 at 2:02
  • $\begingroup$ Note that your first bulleted statement is not quite right, since $2$ is certainly a sum of squares, but doesn’t fall into your form. As to your last question, surely since you can express $13$ as a sum of squares, you can get the corresponding sum for $13m^2$. $\endgroup$ – Lubin May 9 '14 at 2:23

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

  • $\begingroup$ Perhaps even more straightforward to see $325=18^2+1^2$. I guess it depends on which square(s) you think of first. $\endgroup$ – Gerry Myerson May 9 '14 at 13:01
  • 1
    $\begingroup$ This doesn't work for 17 . 17 = 1^2 + 4^2 . Prime factor of 17 is 17 . According to this theorem, it cannot be expressed ! $\endgroup$ – saruftw Oct 14 '15 at 14:38
  • 1
    $\begingroup$ @saru95 But $17$ is not a prime divisor congruent $3$ mod $4$, because it is congruent $1$ mod $4$. The theorem only considers prime divisors congruent $3$ mod $4$. $\endgroup$ – Dietrich Burde Oct 14 '15 at 18:12
  • $\begingroup$ Yes, what i meant was 17 can be expressed as a sum of 2 squares....but as it is not congruent 3 mod 4 .....the above theorem fails for it . The theorem mentions "if and only if" , have a look at that . $\endgroup$ – saruftw Oct 14 '15 at 18:16
  • 6
    $\begingroup$ You are mistaken. The theorem for $n=17$ says that it is indeed a sum of two squares, because all prime divisors $p$ congruent $3$ mod $4$ (there are none !) appear with even multiplicity. Zero is an even number. $\endgroup$ – Dietrich Burde Oct 14 '15 at 18:58

protected by Community Oct 8 '15 at 17:57

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.