# Finding the greatest common divisor in TypeScript

First described in the classic geometry book *Elements*, by the ancient Greek mathematician Euclid (ca. 300 BC, at the book VII, proposition 2), the method of finding de greatest common divisor between the positive numbers $a$ and $b$, being $a > b$ consists on the knowledge that the common divisors of $a$ and $b$ are the same of $a - b$ and $b$. Therefore, we can find this greatest common divisor by replacing the largest number ($a$) by the different between the two numbers ($a - b$), repeatedly, until the two numbers are equal. In TypeScript, we can do that like this:

This method can be very slow if the difference between $a$ and $b$ is too large. Thankfully, there's another method to find the greatest common divisor between two numbers, that can be described as follows:

- In order to find the greatest common divisor between $a$ and $b$, being $a > b$, perform the division between the two numbers. This operation will give a quotient and a remainder (that we will call $q$ and $r$, respectively). Thus, $a$ can be described as $a = q \times b + r$;
- If $r$ is equal to 0, we stop, because we found that the greatest common divisor of $a$ and $b$ is $b$. Otherwise, we go back to step 1, making $b$ the new $a$ and $r$ will be the new $b$.

Now, we can start with the implementation of the algorithm above:

The implementation is very straightforward and can be read exactly as is described in steps 1 and 2. We can make the function simpler, by checking, directly, if $b$ is equal to zero and only doing the remainder operation afterwards. Therefore, if the function receive a $b$ that is equal to zero, we will know that $a$ is the greatest common divisor:

This variant is called *Euclidean algorithm* (in contrast of the first one, which is the *Euclid's algorithm*) and it significantly faster than the first implementation.

## Alternative implementations

We can also take a different approach. Instead of calling our `gcd`

function recursively, we can implement our function using a `while`

loop (analogous to our first implementation above):

And this is another way (analogous to our second implementation above):

## Finding the greatest common between three or more numbers

The greatest of three or more numbers is equal the product of the prime factors common to all the numbers (we will explore more of that in a future article), but, you can also calculate the greatest common divisor between pairs of this list of numbers with the same functions we have showed already. So, let's refactor our `gcd`

function to receive multiple parameters:

## Validating our input

Let's guarantee that our functions should always receive, at least, two numbers and that all numbers must not be negative: