Overview
The Euclidean Algorithm repeatedly replaces (a, b) with (b, a mod b) until the remainder is zero. The last nonzero value is the greatest common divisor.
FoundationSource checked
Euclidean Algorithm
Computes the greatest common divisor of two integers by repeatedly taking remainders.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Numerical Methods
- Difficulty
- Beginner
- Family
- Number Theory
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 9
- Code example
- Ready
- Visualization
- Ready
Core Concepts
greatest common divisorremainderinteger divisibilityloop invariant
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log min(a, b))
Worst
O(log min(a, b))
Space
O(1)
When to Use
- Use it when the greatest common divisor of two integers is needed.
- Use it before reducing ratios or checking coprimality.
- Use extended Euclid when Bezout coefficients or modular inverses are also needed.
When Not to Use
- Avoid it when the input domain is not integer-like.
- Avoid returning signed results without normalizing the gcd convention.
- Avoid it for multiple values without deciding whether to fold pairwise gcds.
What It Does
- Computes greatest common divisors
- Reduces integer pairs using remainders
Use Cases
- Reducing fractions
- Number-theory utilities
- Modular arithmetic preprocessing
Inputs
- Numbers, vectors, matrices, or functions
- Tolerance or precision settings
Outputs
- Computed numeric result
- Residual, factorization, or approximation
Key Formulas (1)
GCD recurrence
gcd(a,b) = gcd(b, a mod b)
gcd(a,b) = gcd(b, a mod b)Reduces the problem until the remainder is zero.
Pseudocode
- 1.Set a and b to the absolute input values.
- 2.While b is not zero:
- 3.Set (a, b) to (b, a mod b).
- 4.Return a.
Canonical Example
- Input
- a = 48, b = 18
- Output
- gcd = 6
- Explanation
- 48 mod 18 = 12, 18 mod 12 = 6, and 12 mod 6 = 0, so the gcd is 6.
Implementation Notes
- Normalize inputs with absolute values if the gcd should be nonnegative.
- Loop while b is not zero, then return a.
- Use the extended algorithm when coefficient tracking is required.
Common Pitfalls
- Forgetting to handle zero inputs.
- Returning a negative gcd when inputs are negative.
- Stopping before the last nonzero remainder is identified.
Interactive Mechanism Walkthrough
Iterative Convergence & State TrajectoryShow repeatedly replacing the larger value with a remainder on a small greatest common divisor example.
Step 1 of 4: Set a and b to the absolute input values.
numerical-methods-mechanismNotes
The algorithm works because replacing a number by its remainder preserves the common divisors of the pair.
Sources (2)
What each reference supports for this entry.
Modern Computer Arithmetic
BookReference for Euclidean Algorithm's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Euclidean Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byFermat Primality Test
Cryptography · Core
Fermat testing may use gcd to detect bases that already share a factor with n.
Compare with thisUsed byPollard's Rho Factorization
Cryptography · Core
Pollard's rho repeatedly uses gcd computations to expose factors.
Compare with thisOften paired withModular Exponentiation
Cryptography · Foundation
GCD checks often appear with modular arithmetic routines.
Compare with thisPrerequisite ofExtended Euclidean Algorithm
Numerical Methods · Foundation
Extended Euclid augments the remainder sequence with coefficient tracking.
Compare with thisRelationships
View full relationship pagePrerequisite ofExtended Euclidean Algorithm
Extended Euclid augments the remainder sequence with coefficient tracking.
GeneralizesBinary GCD
Binary GCD is a specialized gcd method that replaces division with shifts and subtraction.
Often paired withModular Exponentiation
GCD checks often appear with modular arithmetic routines.
Related Algorithms
Tags
Numerical Methods