Function modinverse::egcd

pub fn egcd<T: Copy + Integer>(a: T, b: T) -> (T, T, T)

Finds the greatest common denominator of two integers a and b, and two integers x and y such that ax + by is the greatest common denominator of a and b (Bézout coefficients).

This function is an implementation of the extended Euclidean algorithm.

use modinverse::egcd;

let a = 26;
let b = 3;
let (g, x, y) = egcd(a, b);

assert_eq!(g, 1);
assert_eq!(x, -1);
assert_eq!(y, 9);
assert_eq!((a * x) + (b * y), g);