commands → gcd

gcd(A,B)
gcd(A,B,P)

The gcd command computes the greatest common divisor of A and B, which can be integers or polynomials. An optional third argument P specifies the modulus for polynomial computations modulo a prime.

Examples 

# integers
gcd(10,15);
	5

# polynomials
gcd(x^2-1,x^3-1);
	x-1

# polynomials mod p
gcd(x^2-1,x^3-1,11);
	x+10

Algorithm

The Euclidean algorithm is used for integers. A modular method is used for univariate polynomials.

References

Gullberg, Jan. Mathematics: From the Birth of Numbers. Norton, 1996.