✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-091

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.

NameExpressionDescription

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

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.

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

NameDescription

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

NameDescription

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

NameDescription

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

TitleProblemSolutionAnswer

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