Implementing the Bezout’s Identity in Rust.

Join Medium with my referral link - applied.math.coding

Bezout’s identity is a way to present the greatest common divisor of two integers m, n as linear combination of these two. That is, it ensures the existence of two integers a, b such that

gcd(m, n) = am - bn

A particular useful case is when m, n are relative prime to each other, i.e. gcd(m, n) = 1. This case, we will see, finds an application for implementing the very often used field Z_p.

For more background about Bezout’s identify be referred to this account. There, in particular, we constructed an algorithm that finds a, b from given m, n such that gcd(m, n) = am + bn.

Our mission here, is to implement this algorithm in Rust. For those who need a small wrap-up in Rust, feel invited to an introduction here.

Implementation:

Let us quickly write down the algorithm for the specific type i32. But later, we will generalize this by the use of traits and macros:

// This returns (a, b) such that a*m + b*n = gcd(m,n).
fn bezout_identity(m: i32, n: i32)…