galois.gcd(a: int, b: int) int
galois.gcd(a: Poly, b: Poly) Poly

Finds the greatest common divisor of \(a\) and \(b\).

a: int
a: Poly

The first integer or polynomial argument.

b: int
b: Poly

The second integer or polynomial argument.


Greatest common divisor of \(a\) and \(b\).

See also

egcd, lcm, prod


This function implements the Euclidean Algorithm.



Compute the GCD of two integers.

In [1]: galois.gcd(12, 16)
Out[1]: 4

Generate irreducible polynomials over \(\mathrm{GF}(7)\).

In [2]: GF = galois.GF(7)

In [3]: f1 = galois.irreducible_poly(7, 1); f1
Out[3]: Poly(x, GF(7))

In [4]: f2 = galois.irreducible_poly(7, 2); f2
Out[4]: Poly(x^2 + 1, GF(7))

In [5]: f3 = galois.irreducible_poly(7, 3); f3
Out[5]: Poly(x^3 + 2, GF(7))

Compute the GCD of \(f_1(x)^2 f_2(x)\) and \(f_1(x) f_3(x)\), which is \(f_1(x)\).

In [6]: galois.gcd(f1**2 * f2, f1 * f3)
Out[6]: Poly(x, GF(7))