GCD and LCM (Euclidean Algorithm) 🎯

Welcome to this comprehensive guide on GCD (Greatest Common Divisor) and LCM (Least Common Multiple) using the Euclidean Algorithm! By the end of this tutorial, you'll have a solid understanding of these fundamental concepts, which are crucial for any programmer or computer scientist. Let's dive in!

What are GCD and LCM? 📝

Before we delve into the Euclidean Algorithm, let's first understand the GCD and LCM.

GCD (Greatest Common Divisor)

The GCD of two numbers is the largest number that can evenly divide both numbers. In other words, it's the greatest number that is a factor of both numbers.

LCM (Least Common Multiple)

The LCM of two numbers is the smallest number that is a multiple of both numbers.

The Euclidean Algorithm 💡

The Euclidean Algorithm is a simple, efficient method for finding the GCD of two numbers. It's based on the principle that the GCD of two numbers is the same as the GCD of their difference, if the difference is greater than zero.

Here's a step-by-step breakdown of how the Euclidean Algorithm works:

If the two numbers are the same, their GCD is that number.
If one number is larger than the other, swap them.
Calculate the remainder when the larger number is divided by the smaller number.
Repeat steps 2 and 3 with the smaller number and the remainder until the remainder is zero. The GCD is the number that was swapped in the last iteration.

Practical Examples 🎯

Now, let's put the Euclidean Algorithm into practice!

Example 1: Finding the GCD of 35 and 14

python

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

print(gcd(35, 14))  # Output: 5

Example 2: Finding the LCM of 35 and 14

After finding the GCD, we can easily find the LCM by taking the product of the two numbers and dividing it by the GCD.

python

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

print(lcm(35, 14))  # Output: 490

Quiz Time 💡

Wrapping Up ✅

Congratulations on learning the Euclidean Algorithm for finding the GCD and LCM! These fundamental concepts are essential for data structures and algorithms, and they'll come in handy in numerous real-world projects. Practice the examples provided and try out the quiz to reinforce your understanding. Happy coding!