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 and n, returns (gcd(b, n), a, m) such that a*b + n*m == gcd(b, n).

This implementation is adapted from the sources below:

Extended Euclidean Algorithm on Brilliant.org,
Modular inverse on Rosetta Code,
Algorithm Implementation/Mathematics/Extended Euclidean algorithm on Wikibooks, and
Euclidean algorithm on Wikipedia.

>>> 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