Post Reply 
Sum of Two Squares
09-10-2021, 04:05 PM (This post was last modified: 09-10-2021 05:52 PM by Albert Chan.)
Post: #7
RE: Sum of Two Squares
(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
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
Sum of Two Squares - Eddie W. Shore - 08-17-2019, 01:35 PM
RE: Sum of Two Squares - klesl - 08-17-2019, 07:05 PM
RE: Sum of Two Squares - Eddie W. Shore - 08-20-2019, 05:25 AM
RE: Sum of Two Squares - Eddie W. Shore - 08-18-2019, 05:27 PM
RE: Sum of Two Squares - Albert Chan - 09-09-2021, 11:12 PM
RE: Sum of Two Squares - Albert Chan - 09-10-2021, 02:55 PM
RE: Sum of Two Squares - Albert Chan - 09-10-2021 04:05 PM



User(s) browsing this thread: 1 Guest(s)