egcd

Extended GCD: finds (g, s, t, sub_direction) such that g = gcd(a, b) = s * a - t * b if sub_direction is true, or g = gcd(a, b) = t * b - s * a if sub_direction is false. (s, -t) or (-s, t) are the Bezout coefficients (according to sub_direction). Uses the Extended Euclidean algorithm.

Fully qualified path: core::math::egcd

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