C# Coding Test Course, Extended Euclidean Algorithm

Hello, today we will learn about one of the algorithms that frequently appears in coding tests, which is the Extended Euclidean Algorithm. In this article, we will cover the basic principles of the Extended Euclidean Algorithm, examine problems that utilize it, and discuss how to solve these problems using C#.

1. What is the Extended Euclidean Algorithm?

The Extended Euclidean Algorithm is an algorithm that finds the following two things for two integers a and b:

  1. It calculates the greatest common divisor (gcd(a, b)) of the two numbers a and b.
  2. It expresses that greatest common divisor in the form of integers x and y that correspond to the ratio of a and b. In other words, it can be represented as gcd(a, b) = ax + by.

This algorithm is primarily used for solving modular identities or linear equations. Specifically, it plays an important role in cryptography.

2. Need for the Algorithm

The extended version of the Euclidean Algorithm is a variant of the Euclidean algorithm that can find the greatest common divisor of two numbers through remainder calculations. However, its usefulness shines in the fact that it not only finds the greatest common divisor but also derives it by combining the two numbers. The x and y obtained through this process can be very useful tools in specific problems.

3. Implementation of the Algorithm

First, let’s define a basic C# function to implement the Extended Euclidean Algorithm. This function accepts two integers a and b as arguments and returns the corresponding greatest common divisor along with the values of x and y.


using System;

class Program
{
    static void Main(string[] args)
    {
        int a = 252;
        int b = 105;
        
        var result = ExtendedGCD(a, b);
        Console.WriteLine($"gcd: {result.Item1}, x: {result.Item2}, y: {result.Item3}");
    }

    static (int, int, int) ExtendedGCD(int a, int b)
    {
        if (b == 0)
        {
            return (a, 1, 0);
        }

        var (gcd, x1, y1) = ExtendedGCD(b, a % b);
        
        int x = y1;
        int y = x1 - (a / b) * y1;

        return (gcd, x, y);
    }
}

3.1 Code Explanation

The main part of this code is to implement a function called ExtendedGCD. This function is called recursively to find the greatest common divisor of two numbers:

  • As a base case, when b is 0, the gcd is a, and it returns x as 1 and y as 0.
  • Otherwise, it calls recursively using a and b, and calculates new x and y using the returned values.

4. Example Problem: Finding the GCD and Coefficients

Now, let’s solve a specific problem using the Extended Euclidean Algorithm. For example, given two integers a = 252 and b = 105, we will find their greatest common divisor and the coefficients x, y.

4.1 Problem Definition

For the given two numbers a and b, find the following:

  • gcd(a, b)
  • Find x and y that satisfy gcd(a, b) = ax + by.

4.2 Solution Process

Substituting a = 252 and b = 105 into the given problem, we apply the Extended Euclidean Algorithm. Below is the process:

  1. Call ExtendedGCD(252, 105)
  2. Here b = 105, calling it recursively with ExtendedGCD(105, 252 % 105)
  3. Continuing to call ExtendedGCD(105, 42) where 252 % 105 = 42
  4. Now calling ExtendedGCD(42, 21)
  5. Finally, when we reach ExtendedGCD(21, 0), it returns the greatest common divisor 21, along with the combination x=1, y=0.

During the return process of recursion, the values of x and y are updated one by one, eventually leading us to find gcd(252, 105) = 21 along with the values of x and y. These values are used to express the greatest common divisor as a linear combination of the given numbers.

4.3 Results

The results obtained through this process are as follows:

  • gcd(252, 105) = 21
  • With x = -1 and y = 3, it can be represented as 21 = 252 * (-1) + 105 * 3.

5. Practice Problem

So far, we have looked at the understanding and implementation of the Extended Euclidean Algorithm. Try to implement the Extended Euclidean Algorithm yourself through the following exercise problem.

Exercise Problem

Using the Extended Euclidean Algorithm, find the greatest common divisor and coefficients x, y for the following two integers:

  • a = 119, b = 544

Write your answers and verify them through your implemented C# code!

6. Conclusion

Today, we learned about the Extended Euclidean Algorithm. This algorithm is very useful for finding the greatest common divisor of one or more numbers and can express the result as a linear combination, applying to various mathematical problems. This knowledge is extremely important not only in coding tests but also in actual programming. Before moving on to the next advanced topic, it is recommended to review this algorithm once more and practice through various problems.