The greatest common divisor of two integers is the largest positive integer that divides both without leaving a remainder. It is commonly written as gcd(a, b). One of the most important methods for calculating the GCD is the Euclidean algorithm. This algorithm is based on the observation that gcd(a, b) = gcd(b, a mod b), provided b is nonzero. The process repeatedly replaces the larger problem with a smaller remainder calculation until the remainder becomes zero. The last nonzero remainder is the GCD. The extended Euclidean algorithm goes further by finding integers x and y satisfying ax + by = gcd(a, b). This identity is known as Bézout's identity and has important applications in modular arithmetic. The GCD is also used to simplify fractions, calculate least common multiples, solve linear Diophantine equations, and determine whether a modular multiplicative inverse exists. For multiple integers, the GCD can be calculated by repeatedly applying the two-number GCD operation. The Euclidean algorithm is especially valuable because it avoids the need to list all divisors or fully factor both integers.
Greatest Common Divisor Algorithms and Applications
The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides every integer in the collection. GCD algorithms, particularly the Euclidean algorithm, provide efficient ways to calculate this value.
| Name | Expression | Description |
|---|---|---|
Euclidean algorithm | gcd(a, b) = gcd(b, a mod b) | For b ≠ 0, the GCD remains unchanged when a and b are replaced by b and the remainder of a divided by b. |
Bézout's identity | ax + by = gcd(a, b) | There always exist integers x and y satisfying this equation for integers a and b. |
GCD and LCM relationship | gcd(a, b) × lcm(a, b) = |ab| | For two integers not both zero, the product of their GCD and LCM equals the absolute value of their product. |
Explanation
Variables
| Symbol | Meaning |
|---|---|
a, b | The input integers. |
r | The remainder obtained during a division step. |
x, y | Integers satisfying Bézout's identity. |
gcd(a, b) | The greatest common divisor of a and b. |
lcm(a, b) | The least common multiple of a and b. |
Example or application
A worked example has not yet been added.
Definition
The greatest common divisor of two or more integers, not all zero, is the largest positive integer that divides each of them exactly.
Purpose
To identify the largest shared divisor of integers and provide an efficient foundation for solving divisibility, fraction, and modular arithmetic problems.
Importance
GCD algorithms are fundamental to elementary number theory and computer science. They support fraction simplification, modular inverses, cryptographic calculations, and many algorithms involving integer relationships.
Key Concepts
Common divisor
Greatest common divisor
Euclidean algorithm
Division algorithm
Remainder
Extended Euclidean algorithm
Bézout's identity
Relatively prime integers
Least common multiple
Linear Diophantine equations
Modular inverse
Characteristics
The GCD is always nonnegative under the standard convention.
The GCD of two positive integers divides both numbers.
The Euclidean algorithm repeatedly uses division and remainders.
The last nonzero remainder is the GCD.
The extended Euclidean algorithm also determines Bézout coefficients.
The GCD can be calculated without fully factoring the input integers.
Types
| Name | Description |
|---|---|
Basic divisor method | Finds the common divisors of two integers and selects the greatest one. |
Euclidean algorithm | Uses repeated remainder calculations to determine the GCD efficiently. |
Extended Euclidean algorithm | Calculates the GCD together with integers satisfying Bézout's identity. |
Binary GCD algorithm | Uses comparisons, subtraction, and powers of two to calculate the GCD. |
Components
| Name | Description |
|---|---|
Input integers | The integers whose greatest common divisor is being calculated. |
Division step | Divides one integer by another to determine a quotient and remainder. |
Remainder | The value used to reduce the size of the next GCD calculation. |
Termination condition | The algorithm stops when the remainder becomes zero. |
Bézout coefficients | Integers that express the GCD as a linear combination of the original inputs. |
Properties
gcd(a, b) = gcd(b, a).
gcd(a, 0) = |a| for a nonzero integer.
gcd(a, a) = |a|.
gcd(a, b) = gcd(b, a mod b) when b ≠ 0.
Two integers are relatively prime if and only if their GCD is 1.
The GCD of a collection can be calculated by repeatedly applying the two-integer GCD operation.
A modular inverse of a modulo n exists if and only if gcd(a, n) = 1.
Examples
| Problem | Solution | Result |
|---|---|---|
Find gcd(48, 18) using the Euclidean algorithm. | 48 = 18 × 2 + 12. Then 18 = 12 × 1 + 6. Finally, 12 = 6 × 2 + 0. The last nonzero remainder is 6. | gcd(48, 18) = 6. |
Find integers x and y such that 12x + 8y = gcd(12, 8). | gcd(12, 8) = 4. One valid representation is 12(1) + 8(−1) = 4. | x = 1 and y = −1 are one possible pair of Bézout coefficients. |
Applications
Simplifying fractions
Calculating least common multiples
Finding modular multiplicative inverses
Solving linear Diophantine equations
Cryptographic algorithms
Reducing ratios
Integer and polynomial algorithms
Computer algebra systems
Prerequisites
Integer arithmetic
Divisibility
Division with remainders
Common divisors
Prime factorization
Basic algebra
Learning Objectives
Define the greatest common divisor.
Apply the Euclidean algorithm step by step.
Explain why the Euclidean algorithm preserves the GCD.
Use the extended Euclidean algorithm to obtain Bézout coefficients.
Recognize relatively prime integers.
Explain the relationship between GCD and LCM.
Identify practical uses of GCD algorithms.
Common Mistakes
Choosing a common divisor instead of the greatest common divisor.
Stopping the Euclidean algorithm before the remainder becomes zero.
Reporting zero instead of the last nonzero remainder.
Confusing GCD with LCM.
Assuming that two consecutive integers can have a GCD greater than one.
Forgetting that modular inverses require relatively prime operands and modulus.
Practice Questions
Define the greatest common divisor.
Find gcd(36, 60).
Find gcd(105, 45) using the Euclidean algorithm.
What is the difference between the Euclidean and extended Euclidean algorithms?
State Bézout's identity.
When are two integers relatively prime?
Find the GCD and LCM of 12 and 18.
Why is the GCD important when finding modular inverses?
Key Takeaway
The Euclidean algorithm calculates the greatest common divisor efficiently by repeatedly replacing a pair of integers with a smaller pair while preserving their GCD.
Related Topics
Prime Factorization Algorithms
Least Common Multiple
Bézout's Identity
Modular Arithmetic in Computer Science
Modular Inverses
Linear Diophantine Equations
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory