## 1. Introduction

Calculating the Greatest Common Divisor (GCD) of two numbers is a fundamental operation in number theory and has various applications in computer science and mathematics.

In this tutorial, we’ll explore how to implement a GCD calculation algorithm in Kotlin.

## 2. Greatest Common Divisor

The **GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder**. It is also referred to as the Highest Common Factor (HCF) or the Greatest Common Factor (GCF). **The GCD of any two numbers is never negative or zero as the least positive integer common to any two numbers is always one**.

Here’s the formula to calculate the GCD of two positive integers (*a*, *b*):

*GCD (a,b) = ab/LCM(a,b)*

The Least Common Multiple (LCM) of two or more numbers is simply the smallest multiple that is evenly divisible by all the given numbers. In this formula, we’ll first calculate the product of our integers *a* and *b*, determine their LCM, and finally, divide the product by the LCM.

## 3. Finding the GCD of Two Numbers

There are different algorithms to compute the GCD, and one of the commonly used methods is the Euclidean algorithm, **which by definition computes the Greatest Common Divisor of two integers**.

### 3.1. The Euclidean Algorithm

Let’s go over the definition of the Euclidean algorithm:

*GCD(a, b) = GCD(b, a mod b)*

Now, we’ll use this formula to calculate the GCD of two numbers, a = 48 and b = 18.

We compute the GCD of 48 and 18 by looking at the GCD of 18 and the remainder (12) of 48 divided by 18. Now, we can repeat this process to find the GCD of 18 and 12. Next up, we do the same thing again: express the GCD of 18 and 12 as the GCD of 12 and the remainder (6) of 18 divided by 12. Repeating this process, again we find that the GCD of 12 and 6 is the same as the GCD of 6 and the remainder (0) of 12 divided by 6.

We conclude the process because the remainder has now reached zero. The last non-zero remainder encountered in this series is 6, therefore the GCD of 48 and 18 is 6.

### 3.2. Implementation

Let’s see a code example of the Euclidean algorithm:

```
fun calculateGCD(a: Int, b: Int): Int {
var num1 = a
var num2 = b
while (num2 != 0) {
val temp = num2
num2 = num1 % num2
num1 = temp
}
return num1
}
```

In this code, our *calculateGCD()* function takes two integers, *a* and *b*, as parameters and uses a *while()* loop to continue the Euclidean Algorithm until *num2* becomes zero. Each iteration calculates the remainder of the division *num1 % num2* and updates *num1* and *num2* accordingly. The GCD is the last non-zero value of *num1*.

**Note that it doesn’t matter which number is ***num1* or *num2* initially. The algorithm works by iteratively updating *num1* and *num2* until *num2* becomes zero. We swap the values on each iteration to ensure that *num1* is always the larger number and *num2* is the remainder.

Let’s verify our *calculateGCD()* function with a test:

```
@Test
fun `Should calculate GCD for two integers`() {
assertEquals(6, calculateGCD(18, 48))
assertEquals(1, calculateGCD(17, 5))
assertEquals(9, calculateGCD(27, 18))
assertEquals(15, calculateGCD(75, 45))
}
```

## 4. Finding the GCD of a List of Numbers

Next, we’re going to see how we can calculate the GCD of a list of numbers:

```
fun calculateGCDForListOfNumbers(numbers: List<Int>): Int {
require(numbers.isNotEmpty()) { "List must not be empty" }
var result = numbers[0]
for (i in 1 until numbers.size) {
var num1 = result
var num2 = numbers[i]
while (num2 != 0) {
val temp = num2
num2 = num1 % num2
num1 = temp
}
result = num1
}
return result
}
```

Essentially, our *calculateGCDForListOfNumbers()* function uses the Euclidean algorithm to iteratively calculate the GCD of pairs of *numbers* in the input list, updating the *result* until the entire list is processed. **Finally, the ***result* is the GCD of all the numbers in the list.

At this point, let’s verify our *calculateGCDForListOfNumbers()* function with some tests:

```
@Test
fun `Should calculate GCD for list of two Intergers`() {
val result = calculateGCDForListOfNumbers(listOf(21, 36))
assertEquals(3, result)
}
@Test
fun `Should calculate GCD with three Intergers`() {
val result = calculateGCDForListOfNumbers(listOf(10, 20, 30))
assertEquals(10, result)
}
```

Let’s also confirm that our function throws an exception when the list is empty:

```
@Test
fun `Should fail on empty list`() {
assertFailsWith<IllegalArgumentException> {
calculateGCDForListOfNumbers(emptyList())
}
}
```

To this end, our test proves that *calculateGCDForListOfNumbers()* can’t be called with an empty list. If that happens, an *IllegalArgumentException* is thrown, as expected, enforcing the requirement that the list must not be empty.

## 5. Conclusion

In this article, we’ve defined what the GCD is, and we’ve learned how we can calculate the GCD of two or more integers by leveraging an implementation of the Euclidean algorithm in Kotlin.

The full implementation of these examples is available over on GitHub.