GCD and LCM Euclidean Algorithm in DSA Python - Build from Scratch

GCD and LCM using Euclidean Algorithm

📖 Scenario: Imagine you are helping a friend who wants to find the greatest common divisor (GCD) and least common multiple (LCM) of two numbers. These are useful in many real-life situations like sharing items equally or finding common schedules.

🎯 Goal: You will write a small program that calculates the GCD and LCM of two given numbers using the Euclidean algorithm.

📋 What You'll Learn

Create two integer variables with exact values

Use a variable to hold the original values for calculation

Implement the Euclidean algorithm to find the GCD

Calculate the LCM using the GCD

Print the GCD and LCM in the specified format

💡 Why This Matters

🌍 Real World

Finding GCD and LCM helps in tasks like dividing items equally, scheduling events, and simplifying fractions.

💼 Career

Understanding these algorithms is useful for software developers working on math-related applications, data analysis, and optimization problems.

1

Create two integer variables

Create two integer variables called num1 and num2 with values 48 and 180 respectively.

DSA Python

# Your code here

Hint

Use simple assignment to create num1 and num2.

2

Create copies of the numbers for calculation

Create two new variables called a and b and set them equal to num1 and num2 respectively.

DSA Python

num1 = 48
num2 = 180
# Your code here

Hint

Assign a and b to keep original numbers safe.

3

Calculate the GCD using Euclidean algorithm

Use a while loop with condition b != 0. Inside the loop, create a temporary variable temp to store b, then update b to a % b, and finally update a to temp. This will calculate the GCD and store it in a.

DSA Python

num1 = 48
num2 = 180
a = num1
b = num2
# Your code here

Hint

The Euclidean algorithm repeatedly replaces the larger number by the remainder until the remainder is zero.

4

Calculate and print the GCD and LCM

Create a variable called gcd and set it equal to a. Then calculate the LCM using the formula (num1 * num2) // gcd and store it in a variable called lcm. Finally, print the GCD and LCM in the format: "GCD: <gcd>" and "LCM: <lcm>".

DSA Python

num1 = 48
num2 = 180
a = num1
b = num2
while b != 0:
    temp = b
    b = a % b
    a = temp
# Your code here

Hint

Use integer division // to calculate LCM and print results exactly as shown.

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