egcd module
Easy-to-import library with a basic, efficient, pure-Python implementation of the extended Euclidean algorithm.
- egcd.egcd.egcd(b: int, n: int) Tuple[int, int, int] [source]
Given two integers
b
andn
, returns(gcd(b, n), a, m)
such thata*b + n*m == gcd(b, n)
.This implementation is adapted from the sources below:
>>> egcd(1, 1) (1, 0, 1) >>> egcd(12, 8) (4, 1, -1) >>> egcd(23894798501898, 23948178468116) (2, 2437250447493, -2431817869532) >>> egcd(pow(2, 50), pow(3, 50)) (1, -260414429242905345185687, 408415383037561)
The example below tests the behavior of this function over a range of inputs using the built-in
math.gcd
function.>>> from math import gcd >>> checks = [] >>> for (b, n) in [(b, n) for b in range(200) for n in range(200)]: ... (g, a, m) = egcd(b, n) ... checks.append(g == a*b + n*m) ... checks.append(g == gcd(b, n)) >>> all(checks) True