Euclidean Algorithm (GCD)

DSA · Classic Algorithms

Theory

The Euclidean algorithm finds the greatest common divisor (GCD) of two integers: the largest number that divides both. It relies on one fact: gcd(a, b) = gcd(b, a mod b), because any number dividing a and b also divides the remainder. Repeating this replaces the pair with smaller numbers until the remainder is 0; the other number is then the GCD. For 252 and 105: 252 mod 105 = 42, 105 mod 42 = 21, 42 mod 21 = 0, so the GCD is 21. It is over 2,000 years old and still one of the fastest algorithms known, running in O(log min(a, b)) steps. The least common multiple follows directly: lcm(a, b) = a * b / gcd(a, b). The extended version also finds x and y with ax + by = gcd(a, b), which is used for modular inverses in cryptography.

Why we use it

GCD and LCM appear in fraction simplification, scheduling repeating events, ratio problems and RSA cryptography. The algorithm is also the standard first example of a fast recursive algorithm.

When to use it

Use it whenever you need common divisors or multiples. Python's math.gcd and math.lcm implement it for you.

How it works

  1. gcd(a, b)
  2. b == 0? Yes: Return a. No: (a, b) = (b, a % b).
  3. Repeat

Syntax

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
lcm(a, b) = a * b // gcd(a, b)
Time O(log min(a, b))

Example

import math

def gcd(a, b):
    steps = []
    while b:
        steps.append(f"gcd({a}, {b})")
        a, b = b, a % b
    steps.append(f"= {a}")
    print(" -> ".join(steps))
    return a

gcd(252, 105)
print("math.gcd:", math.gcd(252, 105))

def lcm(a, b):
    return a * b // math.gcd(a, b)
print("Buses every 12 and 18 min meet every", lcm(12, 18), "min")

num, den = 84, 126
g = math.gcd(num, den)
print(f"{num}/{den} simplifies to {num // g}/{den // g}")

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y
g, x, y = extended_gcd(240, 46)
print(f"240*{x} + 46*{y} = {g}")

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic