1 Definition and notation
1.1 Basic definition
The greatest common divisor of two integers is the largest positive integer that divides both numbers exactly. If two integers have no common positive divisor greater than 1, their greatest common divisor is 1. The concept applies naturally to nonzero integers and is usually stated for positive values, with signs ignored because divisibility depends on absolute value.
For example, the greatest common divisor of 12 and 18 is 6, since 6 is the largest number that divides each without remainder. By contrast, the greatest common divisor of 8 and 15 is 1, because they share no larger common divisor.
1.2 Greatest common divisor of multiple integers
The greatest common divisor can also be defined for three or more integers. In that case, it is the largest positive integer dividing every number in the set. For instance, the greatest common divisor of 12, 18, and 30 is 6.
This extension is consistent with the two-integer case: the greatest common divisor of several integers can be found by taking the greatest common divisor of two numbers at a time. If any number in the collection is 0, the greatest common divisor is determined by the nonzero values, provided at least one nonzero integer is present.
1.3 Notation and terminology
Common notation includes gcd(a, b), GCD(a, b), or simply (a, b) in some older mathematical texts. In formal writing, gcd is preferred because it is explicit and widely recognized. The term common divisor refers to any integer dividing each number in a set, while greatest common divisor singles out the largest positive such divisor.
The phrase highest common factor is used in some traditions, especially in elementary arithmetic. Although the wording differs, it refers to the same notion.
2 Divisibility properties
2.1 Common divisors
A common divisor of two integers is any positive integer that divides both. The set of common divisors always includes 1, and may include larger values depending on the numbers involved. The greatest common divisor is the largest element in this set.
Common divisors are closely linked to the prime factors shared by the numbers. If two integers have the same prime factors with comparable multiplicities, their common divisors can be substantial; if not, the set may be small.
2.2 Relationship with multiples
If d is the greatest common divisor of a and b, then both a and b are multiples of d. This means they can be written as a = da' and b = db' for some integers a' and b' that share no common divisor greater than 1. In this way, the greatest common divisor measures the largest common scale factor in the two numbers.
The relationship with multiples is often used in simplification. Dividing both numbers by their greatest common divisor produces a reduced pair with no remaining common factor larger than 1.
2.3 Coprime integers
Two integers are called coprime, or relatively prime, when their greatest common divisor is 1. This does not require either number to be prime; rather, it means they share no nontrivial divisor.
Coprime integers play an important role in arithmetic because many formulas simplify when their greatest common divisor is 1. For example, fractions with coprime numerator and denominator are already in lowest terms.
3 Methods of computation
3.1 Listing factors
For small integers, one direct method is to list all positive factors of each number and identify those they have in common. The largest shared factor is the greatest common divisor.
This approach is simple and intuitive, but it becomes inefficient for large numbers, where the number of factors may be substantial and difficult to enumerate.
3.2 Prime factorization
Another method is to factor each number into primes. The greatest common divisor is then obtained by multiplying the primes that appear in both factorizations, each taken to the smallest exponent present in either number.
For example, 12 = 2² × 3 and 18 = 2 × 3², so their greatest common divisor is 2 × 3 = 6. This method is useful for illustrating the structure of divisibility, though it may be harder to apply when prime factorization is not readily available.
3.3 Euclidean algorithm
The Euclidean algorithm is the standard efficient method for computing the greatest common divisor of two integers. It relies on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its remainder after division by the smaller.
Starting with a and b, one repeatedly performs division with remainder until the remainder becomes 0. The last nonzero remainder is the greatest common divisor.
3.3.1 Recursive form
| In recursive form, the algorithm is expressed as gcd(a, b) = gcd(b, a mod b), with the process repeated until b = 0. At that point, gcd(a, 0) = | a | . |
|---|
This formulation reflects the self-reducing nature of the method and is often used in proofs and computer implementations.
3.3.2 Iterative form
The iterative version performs the same steps in a loop. At each stage, the current pair is replaced by the smaller number and the remainder from division.
The iterative approach is practical for hand computation and software alike because it avoids deep recursion and makes each step explicit.
3.4 Extended Euclidean algorithm
The extended Euclidean algorithm not only finds the greatest common divisor but also expresses it as a linear combination of the original integers. Specifically, it produces integers x and y such that ax + by = gcd(a, b).
This extension is valuable in number theory and algebra, since it gives constructive information beyond the divisor itself. It is commonly used to find modular inverses and to solve linear equations in integers.
4 Fundamental properties
4.1 Commutative and associative properties
The greatest common divisor is commutative: gcd(a, b) = gcd(b, a). It is also associative in the sense that gcd(a, gcd(b, c)) = gcd(gcd(a, b), c). These properties allow the operation to be extended naturally from two numbers to many numbers.
Because of these laws, the order in which numbers are grouped does not affect the final result. This makes gcd a stable tool for combining divisibility information.
4.2 Identity and zero properties
| For any nonzero integer a, gcd(a, a) = | a | . Also, gcd(a, 0) = | a | , since every divisor of a also divides 0. These rules provide the boundary cases for the Euclidean algorithm and similar procedures. |
|---|
The number 1 acts as a multiplicative identity in many arithmetic contexts, but for gcd the relevant identity-like behavior is different: gcd(a, 1) = 1 for every integer a. This reflects the fact that 1 divides every integer.
4.3 Divisibility characterization
An integer d is the greatest common divisor of a and b exactly when d divides both numbers and every other common divisor also divides d. This characterization emphasizes maximality in terms of divisibility rather than size alone.
It provides a powerful conceptual tool. Instead of comparing all common divisors directly, one can verify that a candidate divisor dominates them under divisibility.
4.4 Linear combination property
Any common divisor of a and b also divides every integer linear combination of them, such as ax + by. In particular, the greatest common divisor divides all such combinations.
This property is central in proofs and applications. It explains why the greatest common divisor can be represented as a linear combination and why it governs solvability of many integer equations.
5 Relationship with other arithmetic functions
5.1 Least common multiple
The greatest common divisor is closely related to the least common multiple, which is the smallest positive integer divisible by both numbers. Together, they describe complementary aspects of divisibility: one measures shared factors, the other shared multiples.
For positive integers, the two quantities are linked by a simple product relation. This connection is often used to move between factorization and multiple-based reasoning.
5.1.1 Product formula
For positive integers a and b, gcd(a, b) × lcm(a, b) = ab. This formula follows from prime factorization and shows that the two functions together account for all prime-power contributions in the numbers.
If the greatest common divisor is large, the least common multiple is correspondingly smaller, and vice versa. The identity is widely used in computations and algebraic manipulation.
5.2 Prime factor exponents
In prime factorization, each prime contributes according to the smaller exponent in the greatest common divisor and the larger exponent in the least common multiple. This exponent-based view makes the relationship between the two functions precise.
For example, if one number contains 2³ and the other contains 2¹, then the greatest common divisor includes 2¹ while the least common multiple includes 2³. The same rule applies independently to each prime.
5.3 Bézout's identity
Bézout's identity states that the greatest common divisor of two integers a and b can be written as ax + by for some integers x and y. The coefficients are not unique, but at least one such pair always exists.
This result connects divisibility with linear algebra over the integers. It is one of the most important structural facts about the greatest common divisor and underlies many later theorems.
6 Applications
6.1 Fraction simplification
A common use of the greatest common divisor is reducing fractions to lowest terms. By dividing numerator and denominator by their greatest common divisor, one obtains an equivalent fraction with no common factor greater than 1.
For example, 18/30 simplifies to 3/5 because the greatest common divisor of 18 and 30 is 6. This procedure is standard in arithmetic and algebra.
6.2 Solving linear Diophantine equations
The greatest common divisor determines whether equations of the form ax + by = c have integer solutions. Such a solution exists exactly when the greatest common divisor of a and b divides c.
When a solution does exist, the extended Euclidean algorithm can often produce one directly. From there, all solutions can be described systematically.
6.3 Modular arithmetic
Greatest common divisors are important in modular arithmetic, especially when determining whether an integer has a multiplicative inverse modulo n. An integer a has an inverse modulo n precisely when gcd(a, n) = 1.
This criterion is essential in many calculations involving congruences. It also appears in algorithms for cryptography, although the underlying principle is purely arithmetic.
6.4 Rational number representation
Every rational number can be written as a fraction in reduced form, meaning the numerator and denominator are coprime. The greatest common divisor is what makes this normalization possible.
Reduced representation ensures a unique standard form up to sign conventions. It is useful for comparison, computation, and symbolic manipulation.
7 Generalizations
7.1 GCD for more than two integers
The notion of greatest common divisor extends naturally to any finite collection of integers. The gcd of a set is the largest positive integer dividing every member of the set.
This generalization is often computed pairwise. Because the operation is associative, the result does not depend on the order in which numbers are combined.
7.2 Polynomial greatest common divisor
A corresponding concept exists for polynomials. The greatest common divisor of two polynomials is the polynomial of highest degree, up to multiplication by a nonzero constant, that divides both.
Polynomial gcds are used in algebra, symbolic computation, and the study of roots. Their computation often mirrors the Euclidean algorithm used for integers.
7.3 GCD in algebraic structures
The idea of greatest common divisor can be adapted to more general algebraic settings, such as certain rings. In these contexts, divisibility may behave differently, so the definition must be adjusted to fit the structure.
In some systems, gcds exist and behave much like the integer case; in others, additional conditions are needed. These generalizations help connect elementary number theory with abstract algebra.
8 History
8.1 Ancient origins
The study of common divisors is ancient and appears in early mathematics from several traditions. Questions about measuring quantities, simplifying ratios, and comparing whole-number relationships naturally led to gcd-like ideas.
The concept gained particular prominence in classical Greek mathematics, where arithmetic and geometry were often connected through ratios and divisibility.
8.2 Development of the Euclidean algorithm
The Euclidean algorithm is one of the oldest known computational procedures in mathematics. It is traditionally associated with Euclid’s Elements, where it appears as a systematic method for finding common measures.
Its longevity reflects both its efficiency and its elegance. The algorithm remains central in modern number theory, computer algebra, and educational arithmetic, showing the enduring value of a very old idea.