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