The implementation of Extended Euclidean algorithm.

gcd_ext.rs

use num::{Integer, One, Zero};

pub trait GcdNum: Copy + Integer + One + Zero + std::ops::SubAssign {}

pub fn gcd_ext<T: GcdNum>(
    a: T,
    b: T,
) -> (T, T) {
  fn inner<T: GcdNum>(
      a: T,
      b: T,
      x: &mut T,
      y: &mut T,
  ) -> T {
    if b == T::zero() {
      *x = T::one();
      *y = T::zero();
      a
    } else {
      let d = inner(b, a % b, y, x);
      *y -= a / b * *x;
      d
    }
  }
  let (mut x, mut y) = (T::zero(), T::zero());
  inner(a, b, &mut x, &mut y);
  (x, y)
}