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.
