Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there a general method to expressing integers as the sum of two squares or do you just need to be good with numbers? For example, consider the following problem:

Express 605 as the sum of two squares

Now I believe that a solution to this problem exists because $605 = 5 \cdot 11^2$ and $11 \equiv 3 \pmod 4$ which appears an even number of times and $11$ is the only number in the prime factorization that is congruent to $3 \pmod 4$.

So looking at this problem, what are the first steps that you should take to try and solve this problem? Is there a quick way to go about this?

share|improve this question
4  
Note that $5$ can be written as a sum of two squares (that are easy to find) and that $11^2$ is a square. –  Tobias Kildetoft Apr 19 '13 at 13:14
2  
At least you have nearly given the solution : $605 = 5 . 11 ^ 2$ so $605 = 11^2 + (2.11)^2$... –  Samuel Caillerie Apr 19 '13 at 13:15
    
Nice question and well explained by an example +1 –  DonAntonio Apr 19 '13 at 13:15
    
@SamuelCaillerie, just a little more and that comments of yours could be a very good answer, at least in some wide spectrum of cases. –  DonAntonio Apr 19 '13 at 13:17
    
Just to make this discussion thread more interesting.. Any natural number can be represented as the sum of four integer squares Lagrange's four-square theorem –  freak_warrior Nov 10 '13 at 13:33
add comment

1 Answer 1

up vote 3 down vote accepted

I'm not an expert, but from memory something which it turns out is called the Brahmagupta–Fibonacci identity or occasionally Diophantus identity (used constructively in the proof of the result of Fermat) might be useful: see Wikipedia.

$$\left(a^2 + b^2\right)\left(c^2 + d^2\right) = \left(ac-bd\right)^2 + \left(ad+bc\right)^2 = \left(ac+bd\right)^2 + \left(ad-bc\right)^2$$

This allows you to strip off factors one at a time.

Where you have squares in the factorization, as in the $5\cdot 11^2$ case, note that the square can be factored out as $(p^2+q^2)m^2 = (pm)^2 + (qm)^2$

share|improve this answer
    
For a natural number $n$ and a prime number $p$ let $\deg_p n$ be a maximal integer number $l$ such that $p^l|n$. Then I suppose that there is an expression of $n$ as a sum of two squares (which is obtainable by the above method) iff $\deg_p$ is even for each prime $p$ of the form $4k+1$. –  Alex Ravsky Apr 19 '13 at 13:37
    
I think you can restrict the number of things you have to try but this amounts to experimentation. (Judging by the proofs at en.m.wikipedia.org/wiki/… ) I'll leave it to others to translate these into algorithms, but finding (10,9) in this case I would do by inspection. –  Sharkos Apr 19 '13 at 14:00
    
@Alex Your last sentence should be $4k+3$. –  Calvin Lin Apr 19 '13 at 14:26
    
Yes, it was a mispint. Thanks. –  Alex Ravsky Apr 19 '13 at 14:59
add comment

Your Answer

 
discard

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.