galois.gcd(a, b)

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

Parameters
a

The first integer or polynomial argument.

b

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))
Last update: Sep 02, 2022