Module eea 

Contains multiple variants of the Extended Euclidean Algorithm.

Functions

eea

For a, b computes s, t, d such that s*a + t*b == d is a greatest common divisor of a and b.

gcd

Finds a greatest common divisor of a and b.

half_eeaunstable-enable

Computes the gcd d of a and b, together with “half a Bezout identity”, i.e. some s such that s * a = d mod b.

inv_crt

Computes x such that x = a mod p and x = b mod q. Requires that p and q are coprime.

lcm

Finds the least common multiple of two elements a, b in a euclidean ring, i.e. the smallest (w.r.t. divisibility) element y with a, b | y.

signed_eea

For integers a, b finds the smallest integers s, t so that s*a + t*b == gcd(a, b) is the greatest common divisor of a, b.

signed_gcd

Finds the greatest common divisor of a and b.

signed_lcm

Finds the least common multiple of two elements in an ordered euclidean ring, e.g. of two integers.