GCD and LCM Euclidean Algorithm in DSA Python - Execution Trace

Concept Flow - GCD and LCM Euclidean Algorithm

Start with two numbers a, b

↓

Check if b == 0?

Yes→GCD is a

No↓

Calculate a % b

↓

Set a = b, b = a % b

↓

Repeat until b == 0

↓

Calculate LCM = (original_a * original_b) / GCD

Start with two numbers, repeatedly replace a by b and b by a mod b until b is zero. The last non-zero a is the GCD. Then use GCD to find LCM.

Execution Sample

DSA Python

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

This code finds the GCD of two numbers using the Euclidean algorithm and then calculates their LCM.

Execution Table

Step	Operation	a	b	a % b	Action	GCD So Far	LCM Calculation
1	Start	48	18	N/A	Check b != 0	N/A	N/A
2	Calculate a % b	48	18	12	Set a=18, b=12	N/A	N/A
3	Calculate a % b	18	12	6	Set a=12, b=6	N/A	N/A
4	Calculate a % b	12	6	0	Set a=6, b=0	N/A	N/A
5	b == 0	6	0	N/A	Stop loop, GCD=6	6	N/A
6	Calculate LCM	48	18	N/A	LCM = (48*18)/6 = 144	6	144

💡 Loop stops when b becomes 0; last a is GCD. Then LCM is calculated using GCD.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
a	48	18	12	6	6	6
b	18	12	6	0	0	0
GCD	N/A	N/A	N/A	N/A	6	6
LCM	N/A	N/A	N/A	N/A	N/A	144

Key Moments - 3 Insights

Why do we replace a with b and b with a % b in each step?

Because the GCD of two numbers doesn't change if we replace the larger number by its remainder when divided by the smaller number. This is shown in steps 2-4 where a and b update to smaller values while keeping the GCD same.

Why does the loop stop when b becomes zero?

When b is zero, a holds the GCD. This is clear in step 5 where b=0 and the loop ends, returning a=6 as the GCD.

How is LCM calculated using GCD?

LCM is calculated by multiplying the original two numbers and dividing by their GCD, as shown in step 6: LCM = (48*18)/6 = 144.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'a' after step 3?

A 6

B 18

C 12

D 48

💡 Hint

Check the 'a' column in the execution table row for step 3.

At which step does the condition b == 0 become true, stopping the loop?

A Step 5

B Step 4

C Step 6

D Step 3

💡 Hint

Look at the 'b' column and the 'Operation' column in the execution table.

If the initial numbers were 30 and 12 instead of 48 and 18, how would the final GCD change?

A It would be 12

B It would be 6

C It would be 18

D It would be 30

💡 Hint

Recall the Euclidean algorithm steps and that GCD(30,12) is 6.

Concept Snapshot

GCD(a,b) uses Euclidean algorithm:
Repeat: a,b = b, a % b until b=0
Last a is GCD.
LCM(a,b) = (a*b)//GCD(a,b).
Efficient for large numbers.
No loops run when b=0.

Full Transcript

The Euclidean algorithm finds the greatest common divisor (GCD) of two numbers by repeatedly replacing the larger number with the remainder of dividing it by the smaller number. This continues until the remainder is zero, at which point the other number is the GCD. The least common multiple (LCM) is then found by multiplying the original two numbers and dividing by their GCD. The execution table shows step-by-step how variables a and b change, how the remainder is calculated, and when the loop stops. Key moments clarify why the algorithm updates variables this way, why it stops when b is zero, and how LCM is computed from GCD. The visual quiz tests understanding of variable values at specific steps and the stopping condition.