Sum of two squares

If n = p*q where p and q are primes of the form 4k + 1 then n is a sum of squares. Similarly for more factors.

Primes of the form 4k + 1 can be written as the sum of two squares (uniquely). Then the same is true for a product of such primes. This follows from the identity
(a² + b²)(c² + d²) = (ac – bd)² + (ad + bc)², that is easily proved using complex numbers (of course it is easy to check, once found, by complex numbers lead directly to the result). The proof depends essentially on the fact that the norm is multiplictive:

(a² + b²)(c² + d²) = |a + ib|² * |c + id|² = |(a + ib)(c + id)|² =
= |ac – bd + i(ad + bc)|² = (ac – bd)² + (ad + bc)²

So, provided the prime factors can be written as sum of two squares this identity makes it possible to calculate two squares that sum to the given number. We must first write the primes as sums of two squares, maybe by trial and error, but that should be much easier than trying the whole given number. And we are guaranteed a result at least if all prime factors are of the form 4k + 1. – Of course, if other factors (not prime) are seen to be sums of two squares we can start from them using the above identity.

Examples:
15457 = 13*29*41 = (2² + 3²)(2² + 5²)(4² + 5²) =
= ( (2*2 – 3*5)² + (2*5 + 3*2)² ) * (4² + 5²) = (11² + 16²)(4² + 5²) =
= (11*4 – 16*5)² + (11*5 + 16*4)² = 36² + 119²

25*90 = (3² + 4²)(3² + 9²) = (3*3 – 4*9)² + (3*9 + 4*3)² = 27² + 39²