Greatest Common Divisor

The greatest common divisor of two integers $a$ and $b$ , not both zero, is the largest positive integer that divides both without a remainder. It is usually written $\gcd(a,b)$ . For example, $\gcd(18,24)=6$ , because 6 divides both numbers and no larger positive integer does. The concept is fundamental to number theory, connecting divisibility, the simplification of fractions, and the solution of equations in integers. (math.libretexts.org)

Definition and conventions

An integer $c$ divides an integer $a$ , written $c\mid a$ , if $a=ck$ for some integer $k$ . Thus, for $a$ and $b$ not both zero, their greatest common divisor is the positive integer $d$ satisfying:

$d\mid a$ and $d\mid b$ ;
every common divisor of $a$ and $b$ divides $d$ .

For integers, this characterization is equivalent to being the largest positive common divisor. It also describes the relationship between the GCD and all other common divisors, rather than merely comparing their sizes. (math.libretexts.org)

Signs do not affect the result:

\gcd(a,b)=\gcd(|a|,|b|).

Since every nonzero integer divides zero,

\gcd(a,0)=|a|\qquad(a\ne0).

The pair $(0,0)$ is excluded from the largest-positive-divisor definition: every positive integer divides both entries, so there is no largest one. In an extended convention, $\gcd(0,0)=0$ , making the GCD consistently nonnegative. (math.libretexts.org)

The definition extends to any finite nonempty collection of integers not all zero. Its GCD can be computed successively:

\gcd(a,b,c)=\gcd(\gcd(a,b),c).

Thus $\gcd(12,18,30)=6$ . (aleph0.clarku.edu)

Prime factorization and basic properties

The fundamental theorem of arithmetic gives a factorization-based description. Write positive integers as products of prime numbers, using exponent zero for primes absent from a factorization:

a=\prod_p p^{\alpha_p}, \qquad b=\prod_p p^{\beta_p}.

Then

\gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}.

Each prime occurs in the GCD with the smaller of its two exponents. For example,

72=2^3 3^2,\qquad 120=2^3 3\,5,

so $\gcd(72,120)=2^3 3=24$ . (uregina.ca)

Two integers whose GCD is 1 are called coprime, or relatively prime. Neither integer needs to be prime: 8 and 15 are coprime. For more than two integers, having GCD 1 is weaker than being pairwise coprime. For example, $\gcd(6,10,15)=1$ , although each pair shares a divisor greater than 1. (math.libretexts.org)

The least common multiple uses the larger prime exponent instead. Consequently, for positive integers,

\gcd(a,b)\operatorname{lcm}(a,b)=ab.

The GCD is symmetric and associative, and multiplication of both inputs by a positive integer $k$ gives

\gcd(ka,kb)=k\gcd(a,b).

These properties follow directly from the prime-exponent description. (uregina.ca)

Computing the GCD

The principal method is the Euclidean algorithm, which avoids requiring prime factorizations. Its essential step is

\gcd(a,b)=\gcd(b,r), \qquad a=qb+r.

A number dividing $a$ and $b$ also divides $r=a-qb$ ; conversely, a number dividing $b$ and $r$ divides $a=qb+r$ . The two pairs therefore have exactly the same common divisors. (math.libretexts.org)

For nonnegative inputs with $b>0$ , choose $0\le r<b$ , replace $(a,b)$ by $(b,r)$ , and repeat until the second entry is zero. The decreasing positive remainders ensure termination. The last nonzero remainder is the GCD. For example,

\begin{aligned} 252&=1\cdot198+54,\\ 198&=3\cdot54+36,\\ 54&=1\cdot36+18,\\ 36&=2\cdot18+0. \end{aligned}

Hence $\gcd(252,198)=18$ . (math.libretexts.org)

The binary GCD algorithm instead uses subtraction, comparisons, and the removal of factors of 2. For very large integers, implementations also use methods such as Lehmer’s algorithm and subquadratic GCD algorithms. These illustrate the role of GCD computation in computer science: equivalent mathematical procedures can have different costs depending on input size and machine arithmetic. (gmplib.org)

Bézout’s identity

Bézout’s identity states that, for integers $a,b$ not both zero, there are integers $x,y$ such that

ax+by=\gcd(a,b).

The extended Euclidean algorithm computes these coefficients alongside the GCD, or obtains them by substituting backward through the remainder equations. For the preceding example,

\begin{aligned} 18&=54-36\\ &=54-(198-3\cdot54)\\ &=4(252-198)-198\\ &=4\cdot252-5\cdot198. \end{aligned}

Thus $x=4$ and $y=-5$ . (math.libretexts.org)

Every integer linear combination $ax+by$ is divisible by the GCD. Conversely, Bézout’s identity shows that every multiple of the GCD can be expressed as such a combination. Therefore, the GCD is also the smallest positive integer expressible as $ax+by$ . (math.libretexts.org)

Applications

Reducing fractions. If $b\ne0$ and $d=\gcd(a,b)$ , then

\frac ab=\frac{a/d}{b/d}.

The resulting numerator and denominator are coprime, so the fraction is in lowest terms. For example, $18/24=3/4$ . This provides a standard representation of a rational number, with a positive denominator. (uregina.ca)

Integer equations. A linear Diophantine equation

ax+by=c

has integer solutions exactly when $\gcd(a,b)\mid c$ , provided $a,b$ are not both zero. Necessity follows because the GCD divides every combination $ax+by$ ; sufficiency follows by multiplying a Bézout identity by $c/\gcd(a,b)$ . (math.uwaterloo.ca)

Modular inverses. In modular arithmetic, an integer $a$ has a multiplicative inverse modulo $m>1$ exactly when $\gcd(a,m)=1$ . If $ax+my=1$ , then $ax\equiv1\pmod m$ , making $x$ an inverse. For example, $3\cdot5-7\cdot2=1$ , so 5 is the inverse of 3 modulo 7. (ocw.mit.edu)

Generalization to polynomials

A corresponding concept exists for polynomials. Over a field, a GCD of two nonzero polynomials divides both, and every common polynomial divisor divides it. Multiplication by a nonzero constant does not change these properties, so the result is conventionally normalized to be monic, meaning that its leading coefficient is 1. (doc.sagemath.org)

Polynomial division with remainder supplies a Euclidean algorithm in which degrees decrease instead of integer magnitudes. For example, over the rational numbers,

\gcd(x^2-1,x^2-3x+2)=x-1,

because the factorizations are $(x-1)(x+1)$ and $(x-1)(x-2)$ . Polynomial GCD computations also extend to multivariate polynomials, although they require methods beyond this simple one-variable division procedure. (doc.sagemath.org)

Historical background

Euclid treated the “greatest common measure” in Book VII of *Elements*. Proposition VII.2 gives a procedure for two numbers that are not relatively prime, while VII.3 extends the construction to three numbers. The procedure uses successive subtraction, corresponding to the remainder-based method now called the Euclidean algorithm. The terminology reflects an interpretation of one whole-number quantity as measuring another an exact number of times. (aleph0.clarku.edu)

References

2: Greatest common divisor and least common multiplemath.libretexts.org
6: The Euclidean Algorithmmath.libretexts.org
2: Euclidean algorithm and Bézout's algorithmmath.libretexts.org
Miscellaneous arithmetic functions — SageMathdoc.sagemath.org
Math 101 Course Notesuregina.ca
Greatest Common Divisor Algorithms — GNU MPgmplib.org
MATH 145 Algebra, Lecture Notesmath.uwaterloo.ca
Principles of Discrete Applied Mathematics, Modular Arithmetic and Elementary Algebra Notesocw.mit.edu
Univariate polynomials over number fields — SageMathdoc.sagemath.org
Univariate polynomial base class — SageMathdoc.sagemath.org
Polynomials — SageMath Constructionsdoc.sagemath.org