To express a number as the sum of two squares, prime factorization is very important. Use the Brahmagupta-Fibonacci identity (Diophantus identity) to combine primes. I don't know of a way more efficient than brute force for finding how to express primes (of the form 4n+1) as a sum of two squares. There is also the case (Sum of Two Squares Theorem) of a prime of the form 4n+3 raised to an even power. But those are easy: (p^(n/2))^2 + 0^2.

To know whether a number can be expressed as the sum of 3 squares (Legendre's Three Squares Theorem), first divide out powers of 4, then examine the reminder mod 8. 7 is the problematic remainder: if and only if the remainder is 7, then the original number cannot be expressed as a sum of 3 squares. Otherwise it can be. I don't know of a way more efficient than brute force how one would go about finding the 3 squares if it is possible.

Finally, all numbers can be expressed as a sum of 4 squares (Lagrange Four Squares Theorem), though again, I don't know of efficient way to find one or all the ways a number can be expressed as a sum of 4 squares. Often, there are many ways to express a number as the sum of 4 squares.

## No comments :

Post a Comment