Skip to main content
Computes the extended GCD and Bezout coefficients for two numbers. Uses the Extended Euclidean algorithm to find (g, s, t, sub_direction) where g = gcd(a, b). The relationship between inputs and outputs is:
  • If sub_direction is true: g = s * a - t * b
  • If sub_direction is false: g = t * b - s * a
Returns a tuple (g, s, t, sub_direction) where g is the GCD and (s, -t) or (-s, t) are the Bezout coefficients (according to sub_direction).

​
Signature

pub fn egcd,
    +Drop,
    +Add,
    +Mul,
    +DivRem,
    +core::num::traits::Zero,
    +core::num::traits::One,
    +TryInto>,
>(
    a: NonZero, b: NonZero,
) -> (T, T, T, bool)

​
Examples

use core::math::egcd;

let (g, s, t, dir) = egcd::(12, 8);
assert!(g == 4);