Extended Euclidean Algorithm

egcd(a, b) returns \(g, s, t\) such that \(g = \gcd(a, b)\) and \(as+bt=g\).

Example

fn main() {
for (a, b) in [(2, 5), (11, 17), (20, 35)] {
    let (g, s, t) = egcd(a, b);
    println!("gcd({a}, {b}) = {g}");
    println!("{a}*({s}) + {b}*({t}) = {g}");
}
}

/// Returns `(g, s, t)` such that `g == gcd(a, b)` and `a*s + t*b == g`.
fn egcd(mut a: i64, mut b: i64) -> (i64, i64, i64) {
    let (mut sa, mut ta, mut sb, mut tb) = (1, 0, 0, 1);
    while b != 0 {
        let (q, r) = (a / b, a % b);
        (sa, ta, sb, tb) = (sb, tb, sa - q * sb, ta - q * tb);
        (a, b) = (b, r);
    }
    (a, sa, ta)
}

Code

/// Returns `(g, s, t)` such that `g == gcd(a, b)` and `a*s + t*b == g`.
fn egcd(mut a: i64, mut b: i64) -> (i64, i64, i64) {
    let (mut sa, mut ta, mut sb, mut tb) = (1, 0, 0, 1);
    while b != 0 {
        let (q, r) = (a / b, a % b);
        (sa, ta, sb, tb) = (sb, tb, sa - q * sb, ta - q * tb);
        (a, b) = (b, r);
    }
    (a, sa, ta)
}

Last modified on 231008.