A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.

The Euclidean Algorithm and Greatest Common Divisor

College Depth 89 in the knowledge graph ☐ I know this ☆ Set as goal

5topics build on this

403prerequisites beneath it

Modular Arithmetic and Congruences Divisor Functions and Multiplicative Functions→→The Chinese Remainder Theorem and Its Applications

Core Idea

The Euclidean algorithm efficiently computes gcd(a,b) using repeated division: gcd(a,b) = gcd(b, a mod b), stopping when the remainder is 0. Time complexity is O(log(min(a,b))). The extended Euclidean algorithm finds integers x, y such that ax + by = gcd(a,b).

Explainer

The greatest common divisor gcd(a, b) is the largest integer that divides both a and b. A naive approach — list all divisors of both numbers and find the largest shared one — is painfully slow for large numbers. The Euclidean algorithm exploits a key insight from your prerequisite modular arithmetic: gcd(a, b) = gcd(b, a mod b). This follows because any common divisor of a and b also divides a − qb = a mod b, and vice versa — the set of common divisors is unchanged when you replace a with its remainder mod b.

The algorithm repeatedly applies this reduction: gcd(252, 105) → gcd(105, 42) → gcd(42, 21) → gcd(21, 0) = 21. Each step shrinks the problem: the new pair (b, a mod b) is strictly smaller than (a, b). In the worst case the size halves every two steps, so the total number of steps is O(log(min(a, b))). This logarithmic time complexity makes the algorithm practical for numbers with hundreds of digits — a massive improvement over naive factoring.

The extended Euclidean algorithm goes further: it finds integers x and y such that ax + by = gcd(a, b). This is Bézout's identity. The algorithm works by tracing the computation backwards. For the example above: 21 = 105 − 2(42) = 105 − 2(252 − 2·105) = 5·105 − 2·252, giving x = −2, y = 5. The back-substitution systematically expresses each remainder as a linear combination of the original inputs, and the last nonzero remainder (the GCD) ends up as that combination.

Bézout coefficients are the key to modular inverses: if gcd(a, n) = 1, then ax ≡ 1 (mod n), meaning x is the multiplicative inverse of a modulo n. The extended Euclidean algorithm computes this inverse directly, in O(log n) time. This is why it appears as a core subroutine inside the Chinese Remainder Theorem and RSA cryptography. Understanding the Euclidean algorithm is therefore not just about GCD — it is the computational engine behind much of number-theoretic cryptography and the gateway to the deeper number theory that follows.

Practice Questions 5 questions

Prerequisite Chain

Understanding Zero → The Number Zero → Counting to Five → Counting to 10 → Counting to 20 → Counting a Set of Objects Up to 20 → Cardinality: The Last Number Counted → Matching Numerals to Quantities → Subitizing Small Quantities → Addition Within 10 → Number Bonds to 10 → Addition Within 20 → Doubles and Near Doubles → Doubles Facts Within 10 → Near Doubles Facts Within 20 → Mental Math Strategies for Addition → Mental Math: Adding and Subtracting Tens → Addition Within 100 → Repeated Addition as Multiplication → Multiplication as Equal Groups → Multiplication: Arrays → Basic Multiplication Facts (0s, 1s, 2s, 5s, 10s) → Multiplication Facts Within 100 → Division as Equal Sharing → Division as Grouping (Measurement Division) → Division: Grouping (Repeated Subtraction) Model → Division: Fair Sharing Model → Division as Equal Sharing → Division as Grouping → Basic Division Facts → Division Facts Within 100 → Multiplication and Division Fact Families → Relationship Between Multiplication and Division → Division Facts as Inverse of Multiplication → Remainders and Quotients in Division → Division Word Problems → Multi-Step Word Problems → Solving Multi-Step Word Problems → Multiplication Word Problems → Division Word Problems → Introduction to Long Division → Factors and Multiples → Prime and Composite Numbers → Equivalent Fractions → Relating Fractions and Decimals → Decimal Place Value → Integers and the Number Line → Comparing and Ordering Integers → Absolute Value → Adding Integers → Subtracting Integers → Multiplying Integers → Introduction to Exponents → Order of Operations → Integer Order of Operations → Variable Expressions → The Distributive Property → Variables and Expressions Review → Introduction to Polynomials → Adding and Subtracting Polynomials → Multiplying Polynomials → Factorial → Permutations → Combinations → Counting Principles: Addition and Multiplication Rules → Introduction to Graph Theory → Propositional Logic Foundations → Logical Equivalences → Set Operations: Union, Intersection, and Complement → Proof by Cases → Proving by Cases and Exhaustion → Vacuous Truth and Trivial Cases → Proof by Cases (Proof by Exhaustion) → Mathematical Induction → Divisibility and Greatest Common Divisor → The Fundamental Theorem of Arithmetic → Divisibility Theory (Formal Treatment) → Fundamental Theorem of Arithmetic (Rigorous Proof) → Arithmetic Functions and Multiplicativity → Dirichlet Series and L-Functions → Primes in Arithmetic Progressions (Dirichlet's Theorem) → Distribution of Primes → Introduction to the Riemann Zeta Function → Dirichlet Series and L-Functions → Primes in Arithmetic Progressions (Dirichlet's Theorem) → Wilson's Theorem → Fermat's Little Theorem → Carmichael Function and Carmichael Numbers → Modular Arithmetic and Congruences → The Euclidean Algorithm and Greatest Common Divisor

Longest path: 90 steps · 403 total prerequisite topics

Prerequisites (2)

Modular Arithmetic and Congruenceshard Divisor Functions and Multiplicative Functionssoft

Leads To (1)

The Chinese Remainder Theorem and Its Applicationshard