# 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.

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)`.

--

--

I am a Software Developer - Java, Rust, SQL, TypeScript - with strong interest doing research in pure and applied Mathematics.