greatest common divisor

The greatest common divisor (archaic: greatest common factor) of two integers a and b is the largest integer that divides them both.  This is usually denoted by gcd(a,b), and sometimes by (a,b).  For example, gcd(24,84)=12, gcd(-5,-100)=5, and gcd(46,111)=1.  This is easily expanded to include any number of integers: gcd(27,30,36,81)=3.

Suppose the prime factorization of a is prod p_sup_i ^ e_sub_i, and that of b is prod p_sup_i ^ f_sub_i, then gcd(a,b) is prod p_sup_i ^ min (3_sub_i,f_sub_i).

You might want to take the time to show the following:

This definition is often generalized in other situations.  For example, the greatest common divisor of two polynomials with integer coefficients is the polynomial of highest degree (and largest leading coefficient) that divides them both.

See Also: EuclideanAlgorithm, LCM, RelativelyPrime

Related pages (outside of this work)

Printed from the PrimePages <> © Reginald McLean.