Sum of Two Squares

[Albert Chan]

(08-17-2019 01:35 PM)Eddie W. Shore Wrote:  Given a positive integer n, can we find two non-negative integers x and y such that:

n = x^2 + y^2

If we have 2 pairs,, we can factor n

HOME> SUM2SQ(12349)

{"30^2 + 107^2 = 12349" , "75^2 + 82^2 = 12349"}

gcd(12349, (75-30)^2 + (107-82)^2)
= gcd(12349, 45^2 + 25^2)         // gcd(12349, 5) = 1, pull 5^2 out
= gcd(12349, 9^2 + 5^2 = 106)   // gcd(12349, 2) = 1, pull 2 out
= gcd(12349, 106/2 = 53)            // 12349 = 53 * 233
= 53

Proof:
n = a^2 + b^2 = c^2 + d^2

(a^2 - c^2) = (d^2 - b^2)
(a-c)*(a+c) = (d-b)*(d+b)            // Let f=a-c, f'=a+c, g=d-b, g'=d+b
f f' = g g'

(f^2 + g^2) * (f'^2 + g^2)
= (f f')^2 + g^2*(f^2 + f'^2) + g^4
= (g g')^2 + g^2*(f^2 + f'^2 + g^2)
= g^2 * (f^2 + f'^2 + g^2 + g'^2)
= g^2 * 4n

-> n = (f^2 + g^2) * (f'^2 + g^2) / (4 g^2)

To keep (f^2 + g^2) small, it is better if (a,b) and (c,d) are in same sort order.
Ref: book "Dead Reckoning: calculating without instruments", p64