Sum of Two Squares
|
09-10-2021, 02:55 PM
Post: #6
|
|||
|
|||
RE: Sum of Two Squares
(09-09-2021 11:12 PM)Albert Chan Wrote: n = a^2 + b^2 = c^2 + d^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 |
|||
« Next Oldest | Next Newest »
|
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)