GCD and LCM Euclidean Algorithm in DSA Python

Mental Model

GCD is the biggest number that divides two numbers without leftovers. LCM is the smallest number both can fit into evenly. Euclid's method finds GCD by repeatedly subtracting or dividing until one number becomes zero.

Analogy: Imagine two ropes of different lengths. To find the longest piece you can cut both ropes into equal pieces without leftovers, you keep cutting the longer rope by the length of the shorter until one rope is fully cut. That length is the GCD. Then, the LCM is like finding the smallest length where both ropes can be joined end to end evenly.

a = 48
b = 18

GCD process:
48 -> 18 -> 12 -> 6 -> 0

LCM = (a * b) / GCD

48 -> 18
↑    ↑

Dry Run Walkthrough

Input: Find GCD and LCM of 48 and 18

Goal: Calculate the greatest common divisor and least common multiple of 48 and 18 using Euclid's algorithm

Step 1: Calculate remainder of 48 divided by 18 (48 % 18 = 12)

a = 18, b = 12

Why: Replace a with b and b with remainder to reduce problem size

Step 2: Calculate remainder of 18 divided by 12 (18 % 12 = 6)

a = 12, b = 6

Why: Continue reducing numbers to find GCD

Step 3: Calculate remainder of 12 divided by 6 (12 % 6 = 0)

a = 6, b = 0

Why: When remainder is zero, current a is GCD

Result:

GCD = 6
LCM = (48 * 18) / 6 = 144

Annotated Code

DSA Python

def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b  # reduce problem by remainder
    return a  # when b is zero, a is gcd

def lcm(a: int, b: int) -> int:
    return (a * b) // gcd(a, b)  # lcm from gcd

# Driver code
num1 = 48
num2 = 18
print(f"GCD of {num1} and {num2} is {gcd(num1, num2)}")
print(f"LCM of {num1} and {num2} is {lcm(num1, num2)}")

while b != 0:

loop until remainder is zero to find gcd

a, b = b, a % b # reduce problem by remainder

update a and b to smaller problem using remainder

return a # when b is zero, a is gcd

return gcd when remainder is zero

return (a * b) // gcd(a, b) # lcm from gcd

calculate lcm using gcd

Output

GCD of 48 and 18 is 6

LCM of 48 and 18 is 144

Complexity Analysis

Time: O(log(min(a, b))) because each step reduces the problem size by remainder which shrinks quickly

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Euclid's algorithm is much faster than checking all divisors up to min(a,b), which is O(min(a,b))

Edge Cases

One number is zero (e.g., gcd(0, 5))

GCD is the non-zero number, LCM is zero

DSA Python

while b != 0:

Both numbers are equal (e.g., gcd(7, 7))

GCD is the number itself, LCM is the same number

DSA Python

while b != 0:

One number divides the other exactly (e.g., gcd(12, 4))

GCD is the smaller number, LCM is the larger number

DSA Python

while b != 0:

When to Use This Pattern

When you need to find the greatest common divisor or least common multiple efficiently, look for Euclid's algorithm pattern because it quickly reduces the problem using remainders.

Common Mistakes

Mistake: Using subtraction repeatedly instead of modulo, which is slower
Fix: Use modulo operator (%) to reduce numbers faster

Mistake: Not handling zero inputs correctly, causing infinite loops
Fix: Check for zero and return the other number as gcd immediately

Summary

Finds the greatest common divisor and least common multiple of two numbers using Euclid's fast remainder method.

Use when you need efficient calculation of GCD or LCM for two integers.

The key insight is that GCD of two numbers equals the GCD of the smaller number and the remainder of the larger divided by the smaller.

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