Function egcd
Source pub fn egcd<T: SignedInteger>(a: T, b: T) -> (T, T, T)
Expand description
Computes the extended greatest common divisor.
Returns (gcd, s, t) such that gcd = s * a + t * b.
Unlike gcd, this function is only defined for signed integers as the s and t
coefficients may be negative.
ยงExamples
assert_eq!(egcd(252, 105), (21, -2, 5));
assert_eq!((252 * -2) + (105 * 5), 21);