Skip to content

Instantly share code, notes, and snippets.

@bolshakov

bolshakov/extended_gcd.rb

Created August 7, 2021 14:27
Show Gist options
  • Save bolshakov/fef90c767dbcd1dc6f839066b0ac2355 to your computer and use it in GitHub Desktop.
Save bolshakov/fef90c767dbcd1dc6f839066b0ac2355 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
extended_gcd.rb
def extended_gcd(a, b)
raise ArgumentError unless a >= b and b >= 0 and a + b > 0
if b == 0
d, x, y = a, 1, 0
else
(d, p, q) = extended_gcd(b, a % b)
x = q
y = p - q * (a / b)
end
[d, x, y]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment