Greatest common divisor

related topics
{math, number, function}
{rate, high, increase}

In mathematics, the greatest common divisor (gcd), also known as the greatest common denominator, greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

This notion can be extended to polynomials, see greatest common divisor of two polynomials.

Contents

Overview

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

The greatest common divisor of a and b is written as gcd(ab), or sometimes simply as (ab). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2. Two numbers are called coprime or relatively prime if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

Calculating the gcd

Using prime factorizations

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18, 84), we find the prime factorizations 18 = 2 · 32 and 84 = 22 · 3 · 7 and notice that the "overlap" of the two expressions is 2 · 3; so gcd(18, 84) = 6. In practice, this method is only feasible for small numbers; computing prime factorizations in general takes far too long.

Here is another concrete example, illustrated by a Venn diagram. Suppose it is desired to find the greatest common divisor of 48 and 180. First, find the prime factorizations of the two numbers:

What they share in common is two "2"s and a "3":

Using Euclid's algorithm

A much more efficient method is the Euclidean algorithm, which uses the division algorithm in combination with the observation that the gcd of two numbers also divides their difference: divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Formally, it can be described as:

Full article ▸

related documents
NP (complexity)
Direct product
Polish notation
Binomial theorem
Empty set
Net (mathematics)
Tensor
Affine transformation
Ordered pair
Partially ordered set
Knapsack problem
Grover's algorithm
Graph theory
Normal space
Fundamental theorem of arithmetic
Cyclic group
Selection sort
Topological vector space
B-spline
A* search algorithm
Delaunay triangulation
Pell's equation
Banach space
Sheffer stroke
Befunge
Universal quantification
Free group
Brute force attack
Finite state machine
Optimization (mathematics)