# Implementing the Bezout’s Identity in Rust.

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