自然数/整数 - 関数 - 拡張ユークリッド互除法

概要

\(0\) でない整数の組 \((x, y)\) について、

\[ax + by = c\]

なる整数の組 \((a, b, c)\) を返す. ここで \(c = gcd(x, y)\) .

/// Number - Extended GCD on Integers
/// Solve of a*x + b*y = gcd(x, y)
/// - Args: x, y
/// - Returns: (a, b, gcd(x, y))
pub fn gcd_ex(x: i128, y: i128) -> (i128, i128, i128) {
    if y == 0 {
        (1, 0, x)
    } else {
        let (p, q, g) = gcd_ex(y, x % y);
        (q, p - q * (x / y), g)
    }
}

#[cfg(test)]
mod test_gcd {
    use crate::num::gcd_ex::*;

    #[test]
    fn test_samples() {
        assert_eq!(gcd_ex(3, 6), (1, 0, 3));
        assert_eq!(gcd_ex(3, 1), (0, 1, 1));
    }

    #[test]
    fn test_equality() {
        for x in -4..=4 {
            for y in -4..=4 {
                let (p, q, g) = gcd_ex(x, y);
                assert_eq!(p * x + q * y, g);
            }
        }
    }
}