Euclidean algorithm in C# to find GCD and LCM

I am reading my Elementary Number Theory book by David M. Burton for a course i took at University, MNFMA104 Tallteori at NTNU in Trondheim. I like Number Theory in Math a lot and will look into writing some C# code, starting with this article. This article will look at how we can find the greatest common divisor (gcd). Mathematically speaking, the definition is the following:

Greatest Common Divisor (GCD)

Given two integers a and b, their greatest common divisor (GCD), denoted as d, is the largest positive integer that divides both a and b without leaving a remainder. Note that divides here means there is no remainer.

Formally, if d = gcd(a, b), then:

1. d divides both a and b. This means d | a and d | b.
2. If there is any other integer c that divides both a and b, then c ≤ d. This ensures that d is the greatest such integer.

For example the numbers 12 and 8 can be divided by 4. And we will see that d = gcd(12,8) = 4 next. But first, let's look at the Euclidean algorithm mathematical definition.

Euclidean Algorithm for GCD

Given two integers a and b (where a ≥ b > 0), their greatest common divisor (GCD), denoted as d, can be found using the Euclidean algorithm. The process is as follows:

1. Let a and b be two integers such that a ≥ b and b > 0.
2. Define a sequence of equations r₀, r₁, r₂, …, where r₀ = a and r₁ = b.
3. For i ≥ 0, compute r_i+2 using the division algorithm:

   r_i+2 = r_i mod r_i+1

4. Continue this process until r_n+1 = 0 for some integer n. At this point:

   d = r_n = gcd(a, b)

In summary, the GCD of a and b is the last non-zero remainder obtained through this iterative process:

gcd(a, b) = d

Let's look at C# code to calculate the GDC, we will use the Euclidean algorithm to calculate it.

int Gcd(int a, int b)
{
	int q_n = Math.Abs(a);
	int r_n = Math.Abs(b);
	while (r_n != 0)
	{
		int remainder = q_n % r_n;
		q_n = r_n;
		r_n = remainder;
	}
	return q_n; // returning here the second-last quotient that was non-zero, which is the gcd
}

Calculating the gcd of 12 and 8 gives:

void Main()
{
	int a = 8;
	int b = 12;
	int gcd = Gcd(a, b);
	Console.WriteLine($"Demo - The greatest common divisor - GCD - using the Euclidean algorithm of the numbers : ");
	Console.WriteLine($"d = gcd({a}, {b}) = {gcd}");
    
}

//output 
// Demo - The greatest common divisor - GCD - using the Euclidean algorithm of the numbers : 
// d= gcd(8, 12) = 4

We can also calculate gcd of some bigger numbers. For example, the gcd of the numbers a= 5040 and b = 3780 are 1260. Both numbers 5040 and 3780 are divisible by 1260. We can also use C# patterns in case we want to apply a more functional approach. Together with tuples and C# patterns, the code becomes very compact, especially when we use recursion and tuples to compose the current state of the currend dividend and divisor, the two numbers we consider and get the remainder from.

<summary>
Calculate the greatest common divisor. Recursive C# pattern of GCD (using 'state approach' for tuple)
</summary>
int Gcd(int a, int b) => (a, b) switch
{
    (0, _) => Math.Abs(b),
    (_, 0) => Math.Abs(a),
    _ => GcdV2(b, a % b)
};

Calculating if two number are coprimes

Let's turn attention to coprime numbers a bit. It is a consequence that if the gcd of two numbers a and b, they are said to be relatively prime, or coprime.

In mathematical terms, two integers a and b are said to be coprime (or relatively prime) if their greatest common divisor (gcd) is 1.

Formally, given two integers a and b, a and b are coprime if:

gcd(a, b) = 1

This definition means that the only positive integer that divides both a and b is 1. In other words, they have no common prime factors.

For example, the numbers a = 1234, b = 3417 can be tested if they are coprimes, by calculating the gcd and if the gcd is 1, they are coprime. They have no other common factors than 1, i.e. they are both coprimes or relatively prime. Let's first define a method in C# :

bool AreCoprime(int a, int b) => Gcd(a,b) == 1; 

We can then verify that a = 1234, b = 3417 are relatively prime and the two numbers are relatively prime.

int a1 = 1234, b1 = 3417;
Console.WriteLine($"\nDemo - If two numbers - GCD - are equal to 1, they are co-primes (relative primes)  : ");
Console.WriteLine($"Are {a1} and {b1} coprime? {AreCoprime(a1, b1)}");

The output is:

Demo - If two numbers - GCD - are equal to 1, they are co-primes (relative primes)  : 
Are 1234 and 3417 coprime? True

Calculating the least common multiple (lcm)

The least common multiple - lcm - can be calculated from the gcd for two numbers a and b. The mathematical definition is this:

In mathematics, the least common multiple (LCM) of two integers a and b is the smallest positive integer m such that both a and b divide m without leaving a remainder. Formally, it can be defined as:

LCM(a, b) = |a · b| / GCD(a, b)

where GCD(a, b) is the greatest common divisor of a and b.

Consider the gcd of a= 5040 and b = 3780. We found that the gcd for the two numbers is : gcd(5040, 3780) = 1260 Here is the code for calculating the lcm:

int Lcm(int a, int b) => (a*b)/Gcd(a,b);

int lcm = Lcm(a,b);
Console.WriteLine($"Demo - Least common multiple - lcm: ");	
Console.WriteLine($"lcmd({a}, {b}) = {lcm}");

This outputs:

Demo - Least common multiple - lcm: 
lcm(5040, 3780) = 15120

The number 15120 above is divisible by both a and b, giving 3 and 4 and no remainder, and it is the lowest number which is both divisible, that is - no integer remainder from the division. We write this if we use m for lcm as : m | a and m | b. To calculate the lcm for multiple numbers, we can use:

int Lcm(int[] numbers) { 
	return numbers.Aggregate((a,b) => Lcm(a,b)); 
}

Note that Aggregate method here (from Linq) does not sum, but fold In functional programming, the term "fold" is often used to describe the process of reducing a collection of elements to a single value by iteratively applying a function. In C#, the Aggregate method is essentially a fold operation, as it reduces the array of numbers to a single value (in this case, the GCD or LCM) by applying the specified function. So, using Aggregate to calculate the GCD or LCM of multiple numbers is indeed an example of a fold operation. Example:

int a = 5040;
int b = 3780;
int c = 2520;
Console.WriteLine($"Demo - Least common multiple - lcm: ");
Console.WriteLine($"lcm({a}, {b}, {c}) = {lcm}");

Output is: Demo - Least common multiple - lcm: lcm(5040, 3780, 2520) = 15120

Share this article on LinkedIn.