beginner8 min read·Updated October 14, 2026

GCD (Euclidean Algorithm) Explained: Tracing gcd(24, 18), gcd(5, 0), gcd(17, 13)

Master the Euclidean algorithm with a complete walkthrough of gcd(24,18), gcd(5,0), and gcd(17,13). Build a clear mental model of remainder reduction.

By Learnisim AI·Published October 14, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic division and remainders (modulo operation)
  • Understanding of factors and multiples
Euclidean Algorithm: GCD & LCM Masterclass Shrinking pairs via remainders: gcd(24,18), gcd(5,0), gcd(17,13) 1. The Divisor Bottleneck Naive: list all factors of 24 & 18 24: {1,2,3,4,6,8,12,24} 18: {1,2,3,6,9,18} → Max is 6 Slow for big numbers & crypto scale! 2. Recursive Algorithm gcd(a, b) = gcd(b, a % b) Base Case: gcd(a, 0) = a LCM Formula: lcm(a,b) = (a·b) / gcd(a,b) Trace A: gcd(24, 18) 24 = 1·18 + 6 (rem 6) 18 = 3·6 + 0 (rem 0) GCD(24, 18) = 6 LCM = (24 · 18) / 6 = 72 Geometry: 24×18 grid tiled by 6×6 Trace B: gcd(5, 0) Edge State: b is already 0 Base Case Reached GCD(5, 0) = 5 Zero-safe terminal condition in code Trace C: gcd(17, 13) 17 = 1·13 + 4 13 = 3·4 + 1 GCD(17, 13) = 1 (Coprime) LCM = 17 · 13 = 221 Prime-adjacent pair reduction
gcd(24, 18), gcd(5, 0), gcd(17, 13) overview diagram
Why

Why We Need a Faster Way to Find Common Divisors

Phase 1: The Divisor Search Bottleneck

Imagine you need to find the greatest common divisor for a pair of numbers like 24 and 18, or prime-adjacent numbers like 17 and 13. The naive approach is to list every single factor for both numbers and look for the largest match. For 24, you check . For 18, you check . The overlap gives 6 as our expected result: .
While listing factors works for small numbers, it quickly collapses into a performance nightmare when numbers grow into the millions or billions. Try doing this manual factor breakdown for cryptographic-scale integers, or even handling edge states like our second pair where one number is already zero. Without a systematic shortcut, code written to find common divisors by brute force spends unnecessary CPU cycles checking factors that can never divide both numbers.
We need a method that rapidly shrinks the search space without missing the target. The Euclidean algorithm solves this exact problem by transforming large numbers into smaller remainders until the answer reveals itself effortlessly.
Why We Need a Faster Way to Find Common Divisors Comparing Naive Factor Search vs. The Euclidean Algorithm (gcd(24, 18)) Phase 1: Naive Factor Search (The Bottleneck) Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24 (checks 24 steps) Factors of 18: 1, 2, 3, 6, 9, 18 (checks 18 steps) Largest Match: gcd(24, 18) = 6 Scans every integer down from min(a,b) Performance Collapse on Large Inputs For cryptographic integers (millions of digits), brute-force divisor loops time out instantly. Phase 2: The Euclidean Shortcut (gcd(24, 18)) Step 1: 24 % 18 = 6 Replace (24, 18) with remainder pair (18, 6) Step 2: 18 % 6 = 0 Replace (18, 6) with remainder pair (6, 0) Remainder is 0 → STOP! gcd = 6 Only 2 modulo operations instead of 24 checks! Robust Edge States & Logarithmic Speed Handles edge states like gcd(5, 0) → 5 instantly. Scales logarithmically: gcd(17, 13) → (13,4) → (4,1) → (1,0) → 1 VS
Why We Need a Faster Way to Find Common Divisors diagram
Model

The Geometry of Reduction: Shrinking Pairs Without Losing the Divisor

Phase 2: The Core Reduction Model

When we look at our starting pair (24, 18), finding their greatest common divisor feels like scanning a multiplication table. But what if we change the problem instead of scanning? The fundamental model of the Euclidean algorithm is substitution through remainder: replacing the larger number with the remainder left after dividing it by the smaller number. For our pair (24, 18), dividing 24 by 18 leaves a remainder of 6 (since ).
Why does this work without losing the answer? Any number that divides both 24 and 18 must also divide their difference, and by extension, their remainder 6. If we shrink our working pair to (18, 6), we have not changed the set of common divisors at all! This reduction property lets us handle our other cases smoothly: when we test (5, 0), the second number is already zero, telling us that 5 itself is the greatest common divisor. For (17, 13), the reduction steps (17, 13) (13, 4) (4, 1) (1, 0) strip away multiples until only 1 remains, proving they are coprime.
The Geometry of Reduction: Shrinking Pairs Without Losing the Divisor Core Mental Model: gcd(a, b) = gcd(b, a mod b) Primary Example: gcd(24, 18) Start: (24, 18) 24 = 1 × 18 + 6 Remainder substitution: (18, 6) 18 = 3 × 6 + 0 Base Case Reached: (6, 0) GCD is 6 Why it preserves divisors: Any number dividing 24 & 18 must also divide their remainder 6. Longer Chain: gcd(17, 13) (17, 13) → rem 4 (13, 4) → rem 1 (4, 1) → rem 0 Final Pair: (1, 0) Strips to 1 (Coprime) Fast Collapse Property Even coprime pairs shrink logarithmically to 1. Zero Termination: gcd(5, 0) Second number is 0 Algorithm terminates instantly Result: GCD is 5 gcd(n, 0) = n always The Universal Mechanics 1. Replace larger with remainder 2. Swap positions (b, a mod b) 3. Repeat until second is 0 Common divisors never change!
The Geometry of Reduction: Shrinking Pairs Without Losing the Divisor diagram
Syntax

Syntax and Implementation of the Euclidean Algorithm

Now that we know why shrinking pairs via remainders works geometrically, let's look at how this translates into actual code. To compute gcd(24, 18), we do not need slow, manual subtraction loops. Instead, Python gives us the modulo operator % to jump straight to the remainder in a single step.

Phase 3: Writing the Euclidean Loop

The syntax for the iterative Euclidean algorithm relies on parallel assignment and a simple while loop condition. When evaluating gcd(24, 18), our loop repeatedly swaps with and with until reaches 0.
python
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Testing our working example
print(gcd(24, 18))  # Expected: 6
print(gcd(5, 0))    # Expected: 5
print(gcd(17, 13))  # Expected: 1
A common beginner mistake is forgetting the order of updates or accidentally overwriting before calculating the modulo. Writing a = b and then b = a % b on the next line breaks the swap because the original value of is already lost. Python's tuple unpacking a, b = b, a % b solves this safely by evaluating both sides simultaneously.
python
def gcd(a, b):
    while b != 0:
        # Fill in the parallel assignment for a and b
        pass
    return a
Worked example

Tracing the Euclidean Algorithm on gcd(24, 18), gcd(5, 0), and gcd(17, 13)

Phase 4: Worked Example

Now we put our loop into motion. Let us trace our primary test cases step by step: gcd(24, 18), gcd(5, 0), and gcd(17, 13). We will watch the numbers shrink until the second parameter hits zero, revealing the greatest common divisor as our final return value.

Given

- Pair 1: a = 24, b = 18
- Pair 2: a = 5, b = 0
- Pair 3: a = 17, b = 13

Steps

Tracing Pair 1: gcd(24, 18)
1. Initial state: a = 24, b = 18. Since b != 0, compute remainder = 24 % 18 = 6. Update a = 18, b = 6.
2. Second iteration: a = 18, b = 6. Compute remainder = 18 % 6 = 0. Update a = 6, b = 0.
3. Termination: b == 0. Loop exits, returning a.
Tracing Pair 2: gcd(5, 0)
1. Initial state: a = 5, b = 0. Since b == 0 immediately, the loop never executes.
2. Termination: Returns a directly.
Tracing Pair 3: gcd(17, 13) (Coprime Pair)
1. Initial state: a = 17, b = 13. Compute remainder = 17 % 13 = 4. Update a = 13, b = 4.
2. Second iteration: a = 13, b = 4. Compute remainder = 13 % 4 = 1. Update a = 4, b = 1.
3. Third iteration: a = 4, b = 1. Compute remainder = 4 % 1 = 0. Update a = 1, b = 0.
4. Termination: b == 0. Loop exits, returning a.

Result

- gcd(24, 18) = 6
- gcd(5, 0) = 5
- gcd(17, 13) = 1
- Finally, using our identity , we find .
python
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# Run the trace for our working example
print(f"gcd(24, 18) = {gcd(24, 18)}")
print(f"gcd(5, 0) = {gcd(5, 0)}")
print(f"gcd(17, 13) = {gcd(17, 13)}")
Euclidean Algorithm Worked Examples: Tracing gcd(24, 18), gcd(5, 0), and gcd(17, 13) Pair 1: gcd(24, 18) a = 24, b = 18 24 % 18 = 6 a = 18, b = 6 18 % 6 = 0 a = 6, b = 0 b == 0 (Termination) Returns a = 6 gcd(24, 18) = 6 Pair 2: gcd(5, 0) a = 5, b = 0 b == 0 immediately Loop never executes Returns a directly gcd(5, 0) = 5 Base Case Identity gcd(a, 0) = a Pair 3: gcd(17, 13) 1. a = 17, b = 13 17 % 13 = 4 2. a = 13, b = 4 13 % 4 = 1 3. a = 4, b = 1 4 % 1 = 0 4. a = 1, b = 0 b == 0 (Coprime pair) Returns a = 1 gcd(17, 13) = 1 (Coprime) Every iteration drops the value of b until b hits 0, revealing our greatest common divisor.
Tracing the Euclidean Algorithm on gcd(24, 18), gcd(5, 0), and gcd(17, 13) diagram
Practice

Practice Writing and Tracing the Euclidean Algorithm

Now that you have seen how gcd(24, 18), gcd(5, 0), and gcd(17, 13) boil down through clean modulo steps, it is time to write the code yourself and verify its execution. Replicating the loop structure locks in the memory of how a and b shift roles until b drops to zero. Try implementing the function from scratch and trace what happens when one of your inputs is already smaller than the other, like gcd(18, 24).
python
def compute_gcd(a, b):
    # TODO: Implement the iterative Euclidean algorithm
    pass

# Test your implementation:
# print(compute_gcd(18, 24)) # Should output 6
Apply

Applying GCD and LCM to Cryptographic and Scaling Problems

Phase 6: Apply

We have built, coded, and traced the Euclidean algorithm using our core test pairs: gcd(24, 18) = 6, gcd(5, 0) = 5, and gcd(17, 13) = 1. Now we take this reduction pattern and apply it beyond simple number pairs. A classic computer science application of the greatest common divisor is calculating the Least Common Multiple (LCM) to synchronize periodic events, or simplifying fractions in geometry and graphics rendering.
Recall that the relationship between the greatest common divisor and the least common multiple for any two non-zero integers and is defined by the identity:
Using our familiar working pair (24, 18), we found gcd(24, 18) = 6. Plugging this into our identity gives:
In systems engineering or rhythmic animation, knowing that lcm(24, 18) = 72 means two processes taking 24 and 18 time units respectively will perfectly align every 72 units. Whenever you need to wrap around fixed grid bounds or synchronize periodic loops, the Euclidean algorithm is your core engine.
python
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    return abs(a * b) // gcd(a, b)

# Task: Write a function sync_time(intervals) that takes a list of integer intervals 
# and finds the overall LCM across all of them by iteratively folding the lcm operation.

FAQ

What is the result of gcd(24, 18) using the Euclidean algorithm?
The result is 6. The algorithm computes 24 % 18 = 6, then 18 % 6 = 0, at which point the remainder is 0 and the last non-zero remainder (6) is the GCD.
How does the Euclidean algorithm handle gcd(5, 0)?
When the second argument is 0, the algorithm terminates immediately and returns the first argument, which is 5. Any number divides zero infinitely, so the GCD with zero is the number itself.
What is the time complexity of the Euclidean algorithm?
The Euclidean algorithm runs in logarithmic time, O(log(min(a, b))), because the size of the numbers shrinks rapidly—at least by half every two steps.

Keep learning