6
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\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
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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

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