Skip to main content

signed_eea

feanor_math::algorithms::eea

Function signed_eea 

Source 
pub fn signed_eea<R>(fst: El<R>, snd: El<R>, ring: R) -> (El<R>, El<R>, El<R>)
where
    R: RingStore,
    R::Type: EuclideanRing + OrderedRing,
Expand description

For integers a, b finds the smallest integers s, t so that s*a + t*b == gcd(a, b) is the greatest common divisor of a, b.

Details: s and t are not unique, this function will return the smallest tuple (s, t) (ordered by the total ordering given by (s, t) ≤ (u, v) :<=> |s| ≤ |u| and |t| ≤ |v|). In the case |a| = |b|, there are two minimal elements, in this case, it is unspecified whether this function returns (±1, 0, a) or (0, ±1, a). We define the greatest common divisor gcd(a, b) as the minimal element of the set of integers dividing a and b (ordered by divisibility), whose sign matches the sign of a.

In particular, have

assert_eq!(2, signed_gcd(6, 8, &StaticRing::<i64>::RING));
assert_eq!(0, signed_gcd(0, 0, &StaticRing::<i64>::RING));
assert_eq!(5, signed_gcd(0, -5, &StaticRing::<i64>::RING));
assert_eq!(-5, signed_gcd(-5, 0, &StaticRing::<i64>::RING));
assert_eq!(-1, signed_gcd(-1, 1, &StaticRing::<i64>::RING));
assert_eq!(1, signed_gcd(1, -1, &StaticRing::<i64>::RING));

and therefore signed_eea(6, 8) == (-1, 1, 2), signed_eea(-6, 8) == (-1, -1, -2), signed_eea(8, -6) == (1, 1, 2), signed_eea(0, 0) == (0, 0, 0)