Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

## #1 2012-02-01 08:24:45

TheDude
Member
Registered: 2007-10-23
Posts: 361

### Sum of squares and primes

I was working on this problem http://www.mathisfunforum.com/viewtopic.php?pid=200241#p200241 in the Help Me! section and came across something interesting.  It seems that if a number C has prime factors

It also appears that the opposite is mostly true: if C has a prime factor p that cannot be written as the sum of the squares of two integers then C itself cannot be the sum of the squares of two integers.  The exception is cases where p appears as a factor of C an even number of times, in which case x and y will both also have p as a factor exactly half the number of times that C does.

Is this a well known fact that I'm not aware of, or is there a proof of this somewhere?  It's not at all clear to me why this appears to be true.  For example, 2 can be written 1^2 + 1^2 = 2, and 2^2 + 3^2 = 13.  If we take 2*2*13 = 52 we get 4^2 + 6^2 = 16 + 36 = 52.  The factors 2*2*13 have no obvious relationship with 4 and 6, yet we see that they are connected somehow.  And this is not an isolated case, I tested numbers up to 440 and found no exceptions to this fact aside from the already mentioned case.

Wrap it in bacon

Offline

## #2 2013-04-13 07:05:49

Nehushtan
Member
Registered: 2013-03-09
Posts: 897
Website

### Re: Sum of squares and primes

You might this theorem useful: A prime p can be written as the sum of two integer squares if and only if p ≡ 1 (mod 4).

Last edited by Nehushtan (2013-04-13 07:07:45)

Blog