JavaScript Coding Test Course, Extended Euclidean Algorithm

Hello, everyone! Today, we will learn about one of the important algorithms in coding tests using JavaScript, the Extended Euclidean Algorithm. In this course, we will provide the concept of the Extended Euclidean Algorithm, the problem-solving process using it, and practical code examples.

1. Problem Description

We will define the problem as follows. Given two integers A and B, the task is to find integers X and Y that satisfy AX + BY = GCD(A, B). Here, GCD refers to the greatest common divisor.

Example

Input: A = 30, B = 21

Output: X = 1, Y = -1, GCD = 3

Solution: 30 * 1 + 21 * (-1) = 3

2. Concept Explanation

The Extended Euclidean Algorithm not only calculates the greatest common divisor (GCD) of two integers but also finds specific coefficients from it. This is primarily used in the following formula:

AX + BY = GCD(A, B)

Here, A and B are the given two integers, and X and Y are the integers we want to find. If the GCD is 1, A and B are coprime, and X and Y can also be used to find modular inverses.

3. Approach

We will implement the Extended Euclidean Algorithm based on the general Euclidean algorithm for finding GCD. The main idea of the algorithm is as follows:

  1. Receive two integers A and B as input.
  2. If B is 0, then the GCD is A, and X is 1, Y is 0.
  3. Otherwise, recursively call with B and A % B using the Euclidean algorithm.
  4. Use the results of the recursive call to calculate the values of X and Y.

4. Algorithm Implementation

Below is an example of implementing the Extended Euclidean Algorithm in JavaScript:


function extendedGCD(a, b) {
    if (b === 0) { // Base case
        return { gcd: a, x: 1, y: 0 };
    }
    // Recur with the new parameters b and a % b
    const { gcd, x: x1, y: y1 } = extendedGCD(b, a % b);
    const x = y1;
    const y = x1 - Math.floor(a / b) * y1;
    return { gcd, x, y };
}

// Test the function with example values
const a = 30;
const b = 21;
const { gcd, x, y } = extendedGCD(a, b);
console.log(`GCD: ${gcd}, X: ${x}, Y: ${y}`);

5. Code Explanation

In the above code, we are recursively calculating the GCD. In the base case, when B is 0, the GCD is A, and at that point, X is 1, Y is 0. After that, we calculate new values for X and Y using the returned X and Y values to ultimately get the result we desire.

6. Test Cases

Now let’s test the function with various test cases.


// Test cases
const testCases = [
    { a: 30, b: 21 },
    { a: 48, b: 18 },
    { a: 56, b: 15 },
    { a: 101, b: 10 },
];

testCases.forEach(({ a, b }) => {
    const { gcd, x, y } = extendedGCD(a, b);
    console.log(`A: ${a}, B: ${b} => GCD: ${gcd}, X: ${x}, Y: ${y}`);
});

7. Conclusion

Today, we learned about the Extended Euclidean Algorithm. This algorithm is very useful for finding the greatest common divisor of two integers and for finding specific coefficients related to it. It is especially used in modular arithmetic and complex algorithm problems, so it is important to understand and practice it thoroughly.

I hope the algorithm used in this article will help you in your coding exam preparations. If you have any additional questions, please leave them in the comments!