The Euclidean Algorithm to find the GCD in Rust.

applied.math.coding
3 min readJan 26, 2023

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

--

--

applied.math.coding

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