The greatest common divisor is one of the most important concepts in elementary and advanced number theory. For two integers a and b, not both zero, the greatest common divisor gcd(a, b) is the largest positive integer that divides both numbers without leaving a remainder. For example, the positive divisors of 18 include 1, 2, 3, 6, 9, and 18, while the positive divisors of 30 include 1, 2, 3, 5, 6, 10, 15, and 30. Their greatest common divisor is therefore 6.
Bézout's Identity establishes a deeper relationship between the GCD and integer linear combinations. It states that for any integers a and b, not both zero, there exist integers x and y such that ax + by = gcd(a, b). The integers x and y are called Bézout coefficients. They are not necessarily unique, but at least one pair always exists.
For example, gcd(12, 18) = 6, and 12(−1) + 18(1) = 6. Thus, 6 can be expressed as an integer linear combination of 12 and 18. Bézout's Identity is closely connected to the Euclidean algorithm, linear Diophantine equations, modular inverses, and divisibility. It provides the theoretical foundation for several important computational methods in number theory.
Greatest Common Divisor and Bézout's Identity
The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides all of them. Bézout's Identity states that the GCD of two integers can always be expressed as an integer linear combination of those integers.
| Name | Expression | Description |
|---|---|---|
Greatest Common Divisor | d = gcd(a, b) | The largest positive integer dividing both a and b, when they are not both zero. |
Bézout's Identity | ax + by = gcd(a, b) | There exist integers x and y that express the GCD as a linear combination. |
Coprime Condition | gcd(a, b) = 1 | The integers a and b are relatively prime. |
GCD and LCM Relationship | gcd(a, b) × lcm(a, b) = |ab| | For nonzero integers a and b, the product of their positive GCD and LCM equals the absolute value of their product. |
Explanation
Variables
A, b
The original integers whose greatest common divisor is being calculated.
D
The greatest common divisor gcd(a, b).
X, y
Integers known as Bézout coefficients.
Lcm(a, b)
The least common multiple of a and b.
Example or application
A worked example has not yet been added.
Definition
For integers a and b, not both zero, gcd(a, b) is the greatest positive integer dividing both a and b. Bézout's Identity states that there exist integers x and y satisfying ax + by = gcd(a, b).
Purpose
The purpose of the GCD is to identify the largest common factor of integers. Bézout's Identity explains how this common factor can be represented as a combination of the original integers and provides a foundation for solving integer equations.
Importance
The GCD is fundamental to understanding divisibility and common factors.
Bézout's Identity provides the theoretical basis for solving linear Diophantine equations.
It helps determine whether two integers are relatively prime.
It is essential for finding modular multiplicative inverses.
It is used in simplifying fractions and solving number-theoretic problems.
It supports important algorithms used in computer science and cryptography.
Key Concepts
| Name | Description |
|---|---|
Greatest Common Divisor | The largest positive integer that divides two or more integers exactly. |
Common Divisor | An integer that divides each of the given integers without leaving a remainder. |
Coprime Integers | Two integers are coprime or relatively prime when their greatest common divisor is 1. |
Integer Linear Combination | An expression of the form ax + by, where a, b, x, and y are integers. |
Bézout Coefficients | The integers x and y that express the GCD as ax + by. |
Characteristics
The GCD is conventionally taken to be nonnegative.
For a and b not both zero, gcd(a, b) is always positive.
The GCD divides every integer linear combination of the two integers.
Bézout coefficients always exist, although they are not necessarily unique.
If gcd(a, b) = 1, the integers are relatively prime.
The GCD can be calculated efficiently using the Euclidean algorithm.
The identity also applies when one of the integers is zero, provided the other is nonzero.
Types
| Name | Description |
|---|---|
GCD of Two Integers | The greatest positive integer dividing two given integers. |
GCD of Multiple Integers | The greatest positive integer dividing every integer in a given collection. |
Coprime Pair | A pair of integers whose GCD is 1. |
Bézout Representation | An expression of the GCD as an integer linear combination of the original integers. |
Components
| Name | Description |
|---|---|
Original Integers | The integers a and b whose greatest common divisor is being determined. |
Greatest Common Divisor | The positive common factor d = gcd(a, b). |
Bézout Coefficients | The integers x and y used to represent d as ax + by. |
Linear Combination | The arithmetic expression ax + by that equals the GCD. |
Properties
gcd(a, b) = gcd(b, a).
gcd(a, 0) = |a| for every nonzero integer a.
gcd(a, b) = gcd(|a|, |b|).
gcd(a, b) divides both a and b.
Every common divisor of a and b divides gcd(a, b).
If d divides both a and b, then d divides ax + by for all integers x and y.
If gcd(a, b) = 1, Bézout's Identity gives integers x and y satisfying ax + by = 1.
If d = gcd(a, b), then gcd(a/d, b/d) = 1.
The GCD is associative: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
Examples
| Title | Problem | Solution | Answer |
|---|---|---|---|
Finding the GCD | Find gcd(24, 36). | The positive divisors of 24 include 1, 2, 3, 4, 6, 8, 12, and 24. The positive divisors of 36 include 1, 2, 3, 4, 6, 9, 12, 18, and 36. The largest common divisor is 12. | gcd(24, 36) = 12. |
Verifying Bézout's Identity | Express gcd(12, 18) as an integer linear combination of 12 and 18. | The GCD is 6. Choosing x = −1 and y = 1 gives 12(−1) + 18(1) = −12 + 18 = 6. | 12(−1) + 18(1) = gcd(12, 18) = 6. |
Coprime Integers | Determine whether 14 and 25 are coprime. | The only positive integer dividing both 14 and 25 is 1. Therefore, gcd(14, 25) = 1. | 14 and 25 are coprime. |
Applications
Simplifying fractions into lowest terms.
Solving linear Diophantine equations.
Finding modular multiplicative inverses.
Calculating least common multiples.
Developing efficient integer algorithms.
Studying divisibility and coprime relationships.
Supporting mathematical methods used in public-key cryptography.
Prerequisites
Integer arithmetic
Factors and multiples
Divisibility
Prime factorization
Integer linear combinations
Learning Objectives
Define the greatest common divisor of two or more integers.
Calculate the GCD using common factors or the Euclidean algorithm.
Explain the meaning of Bézout's Identity.
Identify Bézout coefficients for a given pair of integers.
Determine whether two integers are coprime.
Apply Bézout's Identity to linear Diophantine equations.
Explain the relationship between the GCD and LCM.
Common Mistakes
Confusing the greatest common divisor with the least common multiple.
Assuming that Bézout coefficients must be positive.
Believing that Bézout coefficients are always unique.
Forgetting that the GCD is conventionally nonnegative.
Assuming that two consecutive integers can have a common divisor greater than 1.
Using a linear combination without verifying that its coefficients are integers.
Practice Questions
Find gcd(48, 72).
Determine whether 35 and 64 are coprime.
Express gcd(15, 25) as an integer linear combination of 15 and 25.
State and explain Bézout's Identity.
Find integers x and y satisfying 21x + 15y = 3.
Explain why gcd(a, b) divides every integer linear combination of a and b.
How is the GCD related to the LCM of two nonzero integers?
Key Takeaway
The greatest common divisor identifies the largest common factor of integers, while Bézout's Identity proves that this divisor can always be expressed as an integer linear combination of the original numbers. Together, they form a foundation for many important results and algorithms in number theory.
Related Topics
Extended Euclidean Algorithm
Linear Diophantine Equations
Divisibility
Prime Factorization
Coprime Integers
Modular Inverses
Least Common Multiple
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