Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The title says it all. On my homework I am tasked with creating an algorithm that determines whether or not a natural number n can be written as the sum of two squares.

The only stipulation I am given is that I have access to (theoretically) a computer which will quickly tell me if a number k is a perfect square.

I really am just stuck on how to go about doing this, so even just a small hint in the right direction would be appreciated!

share|cite|improve this question
Not helpful for large numbers, but the non-negative integer $n$ is a sum of two squares iff every prime of the form $4k+3$ in the prime factorization of $n$ occurs to an even power. (Am counting $0$ as a perfect square, and allow the two squares to be equal.) – André Nicolas Sep 11 '12 at 3:15
See…. – lhf Sep 11 '12 at 3:28
Whoops, thought I searched far and wide before asking. Sorry about that. – madisonfly Sep 11 '12 at 16:39
up vote 0 down vote accepted

From the description, I guess you're supposed to brute-force it:

while true do
   if b<0 return false
   if b is a perfect square return true
share|cite|improve this answer
If $n$ is $2$ or $3 \pmod 4$ you can return false immediately. – Ross Millikan Sep 11 '12 at 3:45
Should that not be "if $n$ is $3 \pmod{4}$ then return false"? Since $10 \equiv 2 \pmod{4}$ and 10 is a sum of 2 squares. – Old John Sep 11 '12 at 10:19
You can also stop as soon as $b < a^2$ instead of $b<0$. – lhf Sep 11 '12 at 12:03
It might not be a great saving, but we could also divide by any square factors first, since they have no effect on representability by a sum of 2 squares. e.g. if $n\equiv 0 \pmod{4}$, then replace $n$ by $n/4$. – Old John Sep 11 '12 at 23:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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