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.

Practice

1. What does the Euclidean algorithm primarily calculate between two numbers?

easy

A. The difference between the two numbers

B. The least common multiple (LCM)

C. The sum of the two numbers

D. The greatest common divisor (GCD)

Solution

1. Step 1: Understand the Euclidean algorithm purpose

   The Euclidean algorithm is designed to find the greatest common divisor (GCD) of two integers by repeatedly applying division and remainder operations.

2. Step 2: Differentiate GCD from LCM

   While GCD finds the largest number dividing both inputs, LCM finds the smallest number divisible by both. The Euclidean algorithm is specifically for GCD.

3. Final Answer:

   The greatest common divisor (GCD) -> Option D

4. Quick Check:

   Euclidean algorithm = GCD [OK]

Hint: Euclidean algorithm finds GCD, not LCM [OK]

Common Mistakes:

• Confusing GCD with LCM
• Thinking it calculates sum or difference
• Assuming it finds prime factors

2. Which of the following is the correct Python syntax to calculate GCD using the Euclidean algorithm recursively?

easy

A. def gcd(a, b): return a + b if b == 0 else gcd(b, a % b)

B. def gcd(a, b): return a if b == 0 else gcd(b, a % b)

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

D. def gcd(a, b): return b if a == 0 else gcd(a, b % a)

Solution

1. Step 1: Analyze recursive base case and recursive call

   The base case is when b == 0, returning a. Otherwise, call gcd with parameters (b, a % b) to reduce the problem.

2. Step 2: Check each option's correctness

   def gcd(a, b): return a if b == 0 else gcd(b, a % b) matches the correct recursive Euclidean algorithm syntax. def gcd(a, b): return b if a == 0 else gcd(a, b % a) swaps parameters incorrectly. def gcd(a, b): while b != 0: a, b = b, a % b return a is iterative, not recursive. def gcd(a, b): return a + b if b == 0 else gcd(b, a % b) incorrectly adds a and b.

3. Final Answer:

   def gcd(a, b): return a if b == 0 else gcd(b, a % b) -> Option B

4. Quick Check:

   Recursive gcd uses b == 0 base and gcd(b, a % b) call [OK]

Hint: Base case b==0, call gcd(b, a % b) recursively [OK]

Common Mistakes:

• Swapping parameters incorrectly
• Using addition instead of modulo
• Confusing recursive and iterative syntax

3. What is the output of the following Python code?

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

print(gcd(48, 18))

medium

A. 6

B. 12

C. 18

D. 3

Solution

1. Step 1: Trace the while loop iterations

   Start with a=48, b=18. Iteration 1: a=18, b=48%18=12. Iteration 2: a=12, b=18%12=6. Iteration 3: a=6, b=12%6=0. Loop ends.

2. Step 2: Return the final value of a

   When b=0, return a=6, which is the GCD of 48 and 18.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Use modulo until remainder zero; last non-zero divisor is GCD [OK]

Common Mistakes:

• Returning b instead of a
• Confusing modulo with division
• Stopping loop too early

4. Find the error in this Python function to compute LCM using GCD:

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

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

print(lcm(12, 15))

medium

A. No error; output is correct

B. gcd function has wrong loop condition

C. lcm function should add gcd instead of divide

D. lcm function should use gcd(b, a) instead of gcd(a, b)

Solution

1. Step 1: Check gcd function correctness

   The gcd function uses while b (equivalent to while b != 0), swapping a and b and updating b with a % b. This is correct.

2. Step 2: Verify lcm formula correctness

   LCM is calculated as (a * b) divided by gcd(a, b), which is mathematically correct.

3. Final Answer:

   No error; output is correct -> Option A

4. Quick Check:

   LCM formula = (a*b)//GCD(a,b) [OK]

Hint: LCM = (a*b)//GCD(a,b) is correct formula [OK]

Common Mistakes:

• Using addition instead of division in LCM
• Incorrect loop condition in gcd
• Swapping parameters unnecessarily

5. Given two numbers 21 and 6, use the Euclidean algorithm to find their LCM. What is the correct LCM?

hard

A. 126

B. 18

C. 42

D. 36

Solution

1. Step 1: Calculate GCD of 21 and 6 using Euclidean algorithm

   21 % 6 = 3, then 6 % 3 = 0, so GCD is 3.

2. Step 2: Calculate LCM using formula

   LCM = (21 * 6) // 3 = 126 // 3 = 42.

3. Final Answer:

   42 -> Option C

4. Quick Check:

   LCM = (21*6)//GCD(21,6) = 42 [OK]

Hint: LCM = (a*b)//GCD; find GCD first [OK]

Common Mistakes:

• Calculating LCM as product without dividing by GCD
• Mixing up GCD and LCM values
• Incorrect modulo calculations