# The Euclidean Algorithm to find the GCD in Rust.

This story aims at providing the theory behind the Euclidean algorithm and to provide a possible implementation in Rust. For those who need a small wrap-up in Rust, feel invited to this introduction.

The greatest common divisor of two non-negative integers `n, m`

, denoted by `gcd(n, m)`

is defined to by the largest integer that divides both `n`

and `m`

. One can show by considering the prime decomposition of `m`

and `n`

that this definition is equivalent with `d`

being `gcd(n, m)`

if and only if for all integers `k`

that divide `n`

and `m`

also divide `d`

.

In symbols: For any `k`

, `k | n`

and `k | m`

implies `k | d`

.

If this is fulfilled for some `d`

, then `d = gcd(m, n)`

.

This property is used essentially when showing the existence of `gcd(m, n)`

and providing an algorithm to find it.

Let us start with some easy theoretical facts.

Using this proposition we are able to establish an algorithm that determines the `gcd`

of two non-negative integers. In essence it makes use of the Euclidean division — more on that can be found here.

Next, let us provide some possible implementation for this.

## Implementation:

As already laid out, the algorithm essentially uses the recursive relation of `gcd(n, m) = gcd(m — n, n)`

.