Sum of Two Squares

[Albert Chan]

(09-10-2021 02:55 PM)Albert Chan Wrote:  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

Another way, by forcing k=1 ... radical will disappear.

1457 = 37^2 + (2√22)^2 = 7^2 + (8√22)^2

gcd(1457, 30^2+(6√22)^2 = 1692 = 1457+5*47) = 47

This work even for sum of square of radicals.

1457 = 3*2^2 + 5*17^2 = (2√3)^2 + (17√5)^2
1457 = 3*22^2 + 5*1^2 = (22√3)^2 + (√5)^2

gcd(1457, (20√3)^2+(16√5)^2 = 2480 = 2^4*5*31) = 31

Interestingly, gcd(n, a*d ± b*c) seems to work as well.

gcd(1457, 2*1-17*22 = -372 = -2^2*3*31) = 31
gcd(1457, 2*1+17*22 = 376 = 2^3*47) = 47