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

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

Parameters
a: int
a: Poly

The first integer or polynomial argument.

b: int
b: Poly

The second integer or polynomial argument.

Returns

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

See also

egcd, lcm, prod

Notes

This function implements the Euclidean Algorithm.

References

Examples

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