Sum of Two Squares

[Albert Chan]

(09-09-2021 11:12 PM)Albert Chan Wrote:  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'
...
-> n = (f^2 + g^2) * (f'^2 + g^2) / (4 g^2)

Extend this to n = a^2 + k*b^2 = c^2 + k*d^2
Do the math (k=1 should degenerate to above quoted identities)

f f' = k g g'

n = (f^2 + k*g^2) * (f'^2 + k*g^2) / (4k g^2)
   = (2n - 2*(a*c+k*b*d)) * (2n - 2*(a*c-k*b*d)) / (4k g^2)
   = ((a*c + k*b*d) - n) * ((a*c - k*b*d) - n) / (k*g^2)

Numerator must be multiples of n:

(a*c + k*b*d) * (a*c - k*b*d) ≡ 0 (mod n)           // multiply d^2, k*d^2 ≡ -c^2 (mod n)
(a*c*d-b*c^2) * (a*c*d+b*c^2) ≡ 0 (mod n)       // divide by c^2 ≠ 0 (mod n)
(a*d - b*c) * (a*d + b*c) ≡ 0 (mod n/gcd(n,c^2))

gcd(n, a*d ± b*c) produce factor of n

Redo previous example (k=1):

12349 = 30^2 + 107^2 = 75^2 + 82^2

gcd(12349, 30*82-107*75 = -5565) = gcd(5565, 12349-5565 = 6784 = 2^7*53) = 53
gcd(12349, 30*82+107*75 = 10485) = gcd(10485, 12349-10485 = 1864 = 2^3*233) = 233

Now, make k = 15^2 = 225:

12349 = 107^2 + 225*2^2 = 82^2 + 225*5^2

gcd(12349, 107*5-82*2 = 371 = 7*53) = 53
gcd(12349, 107*5+82*2 = 699 = 3*233) = 233

Another example, from "Dead Reckoning", p65, (k = 22)

1457 = 37^2 + 22*2^2 = 7^2 + 22*8^2

gcd(1457, 37*8-2*7 = 282 = 2*3*47) = 47
gcd(1457, 37*8+2*7 = 310 = 2*5*31) = 31