Implementing the Bezout’s Identity in Rust.

4 min readJan 30, 2023

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.


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




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