GCD and LCM Euclidean Algorithm in DSA Javascript - Deep Dive

Overview - GCD and LCM Euclidean Algorithm

What is it?

GCD (Greatest Common Divisor) is the largest number that divides two numbers without leaving a remainder. LCM (Least Common Multiple) is the smallest number that both numbers divide into evenly. The Euclidean Algorithm is a fast way to find the GCD by repeatedly subtracting or dividing numbers. Once GCD is known, LCM can be found easily using a simple formula.

Why it matters

Without a fast way to find GCD and LCM, many tasks like simplifying fractions, scheduling events, or cryptography would be slow and complicated. The Euclidean Algorithm makes these calculations efficient, saving time and resources in real-world applications like computer programs and engineering.

Where it fits

Before learning this, you should understand basic division and multiplication. After this, you can explore number theory topics like prime factorization, modular arithmetic, and cryptographic algorithms.

Mental Model

Core Idea

The Euclidean Algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until zero is reached.

Think of it like...

It's like finding the biggest tile size to cover a floor without cutting tiles by repeatedly measuring leftover space until nothing remains.

  Start with two numbers A and B
  ┌───────────────┐
  │  A, B         │
  └──────┬────────┘
         │
         ▼
  Compute remainder R = A % B
         │
  ┌──────┴────────┐
  │ Is R zero?    │
  └──────┬────────┘
         │No
         ▼
  Replace A with B, B with R
         │
         └─────────────┐
                       ▼
                 Repeat steps
         │
         ┌─────────────┐
         │ Yes (R=0)   │
         └──────┬──────┘
                │
                ▼
          GCD is B

Build-Up - 7 Steps

1

Foundation

Understanding GCD and LCM Basics

Concept: Introduce what GCD and LCM mean with simple examples.

GCD of 8 and 12 is 4 because 4 is the biggest number dividing both without remainder. LCM of 4 and 6 is 12 because 12 is the smallest number both divide evenly. Think of GCD as the biggest shared piece and LCM as the smallest shared container.

Result

Clear understanding of what GCD and LCM represent.

Knowing what GCD and LCM mean helps you see why we need efficient ways to find them.

2

Foundation

Division and Remainder Refresher

Concept: Review how division and remainder work since Euclidean Algorithm depends on them.

When dividing 17 by 5, 5 goes into 17 three times (3 * 5 = 15) with a remainder of 2 (17 - 15). This remainder is key to the Euclidean Algorithm.

Result

Understanding division and remainder operations.

Grasping remainder is essential because the algorithm uses it to reduce the problem step-by-step.

3

Intermediate

Euclidean Algorithm Step-by-Step

🤔Before reading on: do you think the algorithm uses subtraction or division to find the GCD? Commit to your answer.

Concept: Learn how the Euclidean Algorithm uses division and remainder to find GCD efficiently.

To find GCD of 48 and 18: 1. Compute 48 % 18 = 12 2. Replace 48 with 18, 18 with 12 3. Compute 18 % 12 = 6 4. Replace 18 with 12, 12 with 6 5. Compute 12 % 6 = 0 6. When remainder is 0, GCD is the last non-zero divisor, 6.

Result

GCD(48, 18) = 6

Understanding the repeated remainder step shows how the problem size shrinks quickly, making the algorithm fast.

4

Intermediate

Calculating LCM Using GCD

🤔Before reading on: do you think LCM is found by adding or multiplying numbers? Commit to your answer.

Concept: Learn the formula connecting LCM and GCD: LCM(a,b) = (a * b) / GCD(a,b).

For numbers 12 and 18: - GCD is 6 - Multiply 12 * 18 = 216 - Divide 216 by 6 = 36 So, LCM(12, 18) = 36.

Result

LCM(12, 18) = 36

Knowing this formula avoids finding multiples manually and leverages the efficient GCD calculation.

5

Intermediate

Implementing Euclidean Algorithm in JavaScript

🤔Before reading on: do you think the algorithm is best implemented using loops or recursion? Commit to your answer.

Concept: Write JavaScript code to find GCD using recursion and loops.

Recursive version: function gcd(a, b) { if (b === 0) return a; return gcd(b, a % b); } Iterative version: function gcdIter(a, b) { while (b !== 0) { let temp = b; b = a % b; a = temp; } return a; }

Result

Both functions return correct GCD for inputs, e.g., gcd(48,18) returns 6.

Seeing both recursive and iterative forms helps understand the algorithm's flow and choose based on context.

6

Advanced

Handling Edge Cases and Negative Numbers

🤔Before reading on: do you think GCD can be negative or zero? Commit to your answer.

Concept: Learn how to handle zero and negative inputs in GCD and LCM calculations.

GCD is always non-negative. If one number is zero, GCD is the other number. For negative inputs, use absolute values. Example: function gcdSafe(a, b) { a = Math.abs(a); b = Math.abs(b); if (b === 0) return a; return gcdSafe(b, a % b); }

Result

gcdSafe(-48, 18) returns 6; gcdSafe(0, 5) returns 5.

Handling edge cases prevents bugs and ensures the algorithm works correctly in all situations.

7

Expert

Optimizations and Algorithm Variants

🤔Before reading on: do you think Euclidean Algorithm can be improved further? Commit to your answer.

Concept: Explore faster variants like Binary GCD Algorithm and understand when to use them.

Binary GCD uses bit operations instead of division: - If both numbers even, GCD doubles and numbers halve. - If one even, halve it. - If both odd, subtract smaller from larger. This reduces division cost. Example code: function binaryGCD(a, b) { if (a === b) return a; if (a === 0) return b; if (b === 0) return a; if ((a & 1) === 0 && (b & 1) === 0) return binaryGCD(a >> 1, b >> 1) << 1; if ((a & 1) === 0) return binaryGCD(a >> 1, b); if ((b & 1) === 0) return binaryGCD(a, b >> 1); if (a > b) return binaryGCD((a - b) >> 1, b); return binaryGCD((b - a) >> 1, a); }

Result

binaryGCD(48, 18) returns 6 faster on some systems.

Knowing algorithm variants helps optimize performance in critical applications.

Under the Hood

The Euclidean Algorithm works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. This process reduces the problem size quickly because the remainder is always smaller than the divisor. Eventually, the remainder becomes zero, and the divisor at that step is the GCD. This relies on the mathematical fact that GCD(a, b) = GCD(b, a % b).

Why designed this way?

Before Euclid, finding GCD involved listing all divisors, which is slow. Euclid's method uses division to reduce the problem size efficiently. It was designed to minimize steps and avoid factorization, which is costly. Alternatives like prime factorization exist but are slower for large numbers.

  Start: a, b
    │
    ▼
  Compute r = a % b
    │
    ├─ If r == 0 -> GCD is b
    │
    └─ Else replace a = b, b = r
          │
          ▼
       Repeat

Myth Busters - 4 Common Misconceptions

Quick: Do you think GCD of two numbers can be zero? Commit yes or no.

Common Belief: GCD can be zero if one or both numbers are zero.

Reality: GCD is never zero. If one number is zero, GCD is the absolute value of the other number. If both are zero, GCD is undefined.

Why it matters: Misunderstanding this causes errors in programs that don't handle zero inputs properly.

Quick: Do you think LCM is always larger than both numbers? Commit yes or no.

Common Belief: LCM is always bigger than both numbers.

Reality: LCM can be equal to one of the numbers if one divides the other exactly.

Why it matters: Assuming LCM is always larger can lead to wrong assumptions in scheduling or synchronization problems.

Quick: Do you think Euclidean Algorithm requires prime factorization? Commit yes or no.

Common Belief: Euclidean Algorithm finds GCD by factoring numbers into primes.

Reality: It uses division and remainder operations, not prime factorization, making it much faster.

Why it matters: Believing prime factorization is needed leads to inefficient solutions and confusion about the algorithm's speed.

Quick: Do you think negative numbers affect the GCD result? Commit yes or no.

Common Belief: GCD can be negative if inputs are negative.

Reality: GCD is always non-negative; negative inputs are converted to positive before calculation.

Why it matters: Ignoring this causes inconsistent results and bugs in mathematical computations.

Expert Zone

1

The Euclidean Algorithm's efficiency comes from the fact that the remainder decreases at least by half every two steps on average.

2

Binary GCD algorithm is often faster on computers because it replaces division with bit shifts and subtraction, which are cheaper operations.

3

In cryptography, GCD calculations are foundational for algorithms like RSA key generation, where large numbers are involved.

When NOT to use

For extremely large numbers in cryptography, specialized algorithms like the Extended Euclidean Algorithm or probabilistic methods may be preferred. Also, if prime factors are needed explicitly, prime factorization methods are necessary.

Production Patterns

In production, GCD and LCM calculations are used in scheduling systems to find common intervals, in simplifying fractions in calculators, and in cryptographic libraries for key generation and validation.

Connections

Extended Euclidean Algorithm

Builds-on

Understanding the Euclidean Algorithm is essential to grasp the Extended version, which also finds coefficients to express GCD as a linear combination.

Modular Arithmetic

Builds-on

Euclidean Algorithm uses the remainder operation, which is the core of modular arithmetic, a foundation for many cryptographic and algorithmic problems.

Signal Processing

Analogous pattern

Finding common frequencies in signals is similar to finding LCM of periods; understanding GCD and LCM helps in analyzing repeating patterns in signals.

Common Pitfalls

#1 Not handling zero inputs correctly.

Wrong approach:

function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
// gcd(0, 5) returns 0 incorrectly

Correct approach:

function gcd(a, b) {
if (a === 0) return Math.abs(b);
if (b === 0) return Math.abs(a);
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return Math.abs(a);
}
// gcd(0, 5) returns 5 correctly

Root cause:

Not checking for zero inputs causes the loop to return zero instead of the non-zero number.

#2 Ignoring negative inputs leading to negative GCD.

Wrong approach:

function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
// gcd(-12, 18) returns -6 incorrectly

Correct approach:

function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
// gcd(-12, 18) returns 6 correctly

Root cause:

Not converting inputs to absolute values causes negative results.

#3 Calculating LCM without using GCD leads to inefficient code.

Wrong approach:

function lcm(a, b) {
let max = Math.max(a, b);
let lcm = max;
while (true) {
if (lcm % a === 0 && lcm % b === 0) return lcm;
lcm++;
}
}
// Very slow for large numbers

Correct approach:

function gcd(a, b) {
a = Math.abs(a);
b = Math.abs(b);
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}

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

Root cause:

Not leveraging the relationship between GCD and LCM causes slow brute force search.

Key Takeaways

The Euclidean Algorithm efficiently finds the greatest common divisor by using division remainders to reduce problem size step-by-step.

Once GCD is known, the least common multiple can be calculated quickly using the formula LCM(a,b) = (a * b) / GCD(a,b).

Handling edge cases like zero and negative inputs is essential for correct and robust GCD and LCM calculations.

Variants like the Binary GCD Algorithm optimize performance by replacing division with bit operations.

Understanding GCD and LCM is foundational for advanced topics like modular arithmetic, cryptography, and scheduling problems.

Practice

1. What does the Euclidean algorithm primarily calculate when given two positive integers a and b?

easy

A. The difference between a and b

B. The least common multiple (LCM) of a and b

C. The sum of a and b

D. The greatest common divisor (GCD) of a and b

Solution

1. Step 1: Understand the Euclidean algorithm purpose

   The Euclidean algorithm is a method to find the greatest common divisor (GCD) of two numbers by repeatedly applying the remainder operation.

2. Step 2: Differentiate GCD from LCM

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

3. Final Answer:

   The greatest common divisor (GCD) of a and b -> Option D

4. Quick Check:

   Euclidean algorithm = GCD [OK]

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

Common Mistakes:

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

2. Which of the following JavaScript function definitions correctly implements the Euclidean algorithm to find the GCD of two numbers a and b?

easy

A. function gcd(a, b) { return a + b; }

B. function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; }

C. function gcd(a, b) { return Math.min(a, b); }

D. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; }

Solution

1. Step 1: Analyze the correct Euclidean algorithm loop

   function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; } uses a while loop that continues until b is zero, swapping values and using modulo to find remainder, which matches the Euclidean algorithm.

2. Step 2: Check other options for correctness

   function gcd(a, b) { return a + b; } returns sum, not GCD. function gcd(a, b) { return Math.min(a, b); } returns minimum, not GCD. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; } has incorrect variable updates causing infinite loop or wrong result.

3. Final Answer:

   function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; } -> Option B

4. Quick Check:

   Correct Euclidean loop = function gcd(a, b) { while(b !== 0) { let temp = b; b = a % b; a = temp; } return a; } [OK]

Hint: Use while loop with modulo and swap variables [OK]

Common Mistakes:

• Returning sum or min instead of GCD
• Incorrect variable swapping causing infinite loops
• Using wrong loop conditions

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

function gcd(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

console.log(gcd(48, 18));

medium

A. 3

B. 12

C. 6

D. 18

Solution

1. Step 1: Trace the Euclidean algorithm steps for gcd(48, 18)

   48 % 18 = 12, then gcd(18, 12); 18 % 12 = 6, then gcd(12, 6); 12 % 6 = 0, then gcd(6, 0) = 6.

2. Step 2: Return the last non-zero remainder

   When second number becomes zero, the first number is the GCD, which is 6 here.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   GCD(48,18) = 6 [OK]

Hint: Apply modulo repeatedly until remainder is zero [OK]

Common Mistakes:

• Stopping too early and returning wrong remainder
• Confusing modulo with division
• Mixing up order of parameters

4. The following code attempts to compute the LCM of two numbers using their GCD. Identify the bug:

function gcd(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}

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

console.log(lcm(4, 6));

medium

A. The gcd function modifies a and b directly, affecting lcm calculation

B. The lcm function should add instead of multiply a and b

C. The gcd function should return b instead of a

D. There is no bug; the code correctly calculates LCM

Solution

1. Step 1: Understand variable mutation in gcd function

   The gcd function changes a and b inside the loop, so after calling gcd, a and b in lcm are modified.

2. Step 2: Impact on lcm calculation

   Since a and b are changed by gcd, the multiplication a * b in lcm uses modified values, causing incorrect LCM.

3. Final Answer:

   The gcd function modifies a and b directly, affecting lcm calculation -> Option A

4. Quick Check:

   Mutating inputs in gcd breaks lcm formula [OK]

Hint: Avoid changing input variables when computing GCD for LCM [OK]

Common Mistakes:

• Assuming gcd doesn't change inputs
• Using addition instead of multiplication in LCM
• Returning wrong variable from gcd

5. Given an array of positive integers [12, 15, 20], which JavaScript function correctly computes the LCM of all elements using the Euclidean algorithm for GCD?

hard

A. function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

B. function gcd(a, b) { return a + b; } function lcm(a, b) { return a * b; } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

C. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; } function lcm(a, b) { return (a + b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

D. function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) * gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20]));

Solution

1. Step 1: Verify gcd and lcm functions correctness

   function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); uses correct Euclidean gcd and calculates lcm as (a*b)/gcd(a,b), which is mathematically correct.

2. Step 2: Check lcmArray function logic

   It uses reduce to apply lcm pairwise across the array, correctly computing LCM of all elements.

3. Step 3: Validate other options

   function gcd(a, b) { return a + b; } function lcm(a, b) { return a * b; } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); uses incorrect gcd and lcm formulas. function gcd(a, b) { while(a !== 0) { a = b % a; b = a; } return b; } function lcm(a, b) { return (a + b) / gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); has wrong gcd and lcm formulas. function gcd(a, b) { while(b !== 0) { let t = b; b = a % b; a = t; } return a; } function lcm(a, b) { return (a * b) * gcd(a, b); } function lcmArray(arr) { return arr.reduce((acc, val) => lcm(acc, val)); } console.log(lcmArray([12, 15, 20])); incorrectly multiplies gcd in lcm formula.

4. Final Answer:

   Option A code correctly computes LCM of array elements -> Option A

5. Quick Check:

   Correct gcd, lcm, and reduce for array LCM [OK]

Hint: Use reduce with correct gcd and lcm formulas for arrays [OK]

Common Mistakes:

• Incorrect gcd or lcm formulas
• Not using reduce to combine array elements
• Multiplying gcd instead of dividing in lcm