GCD and LCM (Euclidean) 🎯

Welcome to another exciting lesson on Data Structures and Algorithms at CodeYourCraft! Today, we're going to learn about two fundamental mathematical concepts: Greatest Common Divisor (GCD) and Least Common Multiple (LCM). These concepts are essential in various programming problems and real-world applications. Let's dive right in! 📝

What is GCD (Greatest Common Divisor)? 💡

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that can divide both numbers without leaving a remainder. In simpler terms, it's the largest number that both numbers share as a factor.

Example:

Let's find the GCD of 48 and 18:

List all the common factors of 48 and 18: 1, 2, 3, 6, 9, 12, 18, 24, 36, 48.
The largest common factor is 18. So, the GCD of 48 and 18 is 18. ✅

What is LCM (Least Common Multiple)? 💡

The Least Common Multiple (LCM) of two integers is the smallest positive integer that is a multiple of both numbers. In simpler terms, it's the smallest number that both numbers can divide evenly into.

Example:

Let's find the LCM of 48 and 18:

Find the highest power of the smallest prime factor that divides both numbers:
- 48: 2³ * 3
- 18: 2² * 3
The highest power of 3 is the same in both numbers (3). The highest power of 2 is the maximum between 2³ and 2² (2³).
So, the LCM of 48 and 18 is 2³ * 3² = 108. ✅

GCD and LCM using Euclidean Algorithm 💡

The Euclidean algorithm is a method to find the GCD and LCM of two numbers efficiently. Let's understand how it works for finding GCD first.

Finding GCD using Euclidean Algorithm:

If a is greater than b, swap a and b.
Let r be the remainder when a is divided by b.
Replace a with b and b with r.
Repeat steps 2 and 3 until r is zero. The last non-zero value of b is the GCD.

Finding LCM using Euclidean Algorithm:

Compute the GCD using the Euclidean algorithm. Let's call it g.
The LCM is |a*b| / g.

Code Examples 💡

Here are code examples in Python and JavaScript demonstrating the Euclidean algorithm for finding GCD and LCM.

Python:

python

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

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

print("GCD:", gcd(48, 18))  # Output: 18
print("LCM:", lcm(48, 18))  # Output: 108

JavaScript:

javascript

function gcd(a, b) {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}

console.log("GCD:", gcd(48, 18));  // Output: 18
console.log("LCM:", lcm(48, 18));  // Output: 108

Wrapping Up 📝

You've now learned about GCD and LCM, their significance, and how to find them using the Euclidean algorithm. Remember to practice these concepts with various examples to make them second nature. Happy coding! 🚀