Extended Euclidean Algorithm

Math / Number Theory O(log min(a, b)) O(1)

Runs Euclid while tracking Bézout coefficients, so it ends with gcd(a, b) = x·a + y·b — the key to modular inverses.

q	r	s	t
—	240	1	0
—	46	0	1

abevery row keeps r = s·a + t·b

1/12

Seed two rows: 240 = 1·a + 0·b and 46 = 0·a + 1·b — every row keeps r = s·a + t·b.

InvariantEvery row satisfies r = s·a + t·b, so when r reaches the gcd the coefficients come with it.

extended-euclidean.c

void extendedGcd(int a, int b) {
    int old_r = a, r = b;
    int old_s = 1, s = 0;     /* coeff of a */
    int old_t = 0, t = 1;     /* coeff of b */
    while (r != 0) {
        int q = old_r / r;
        int tmp;
        tmp = old_r - q*r; old_r = r; r = tmp;
        tmp = old_s - q*s; old_s = s; s = tmp;
        tmp = old_t - q*t; old_t = t; t = tmp;
    }
    printf("gcd = %d = %d*a + %d*b\n",
           old_r, old_s, old_t);
}

How Extended Euclidean Algorithm works

Run Euclid while carrying two extra sequences so that every remainder stays expressed as x·a + y·b. When the remainder hits gcd, its coefficients are the Bézout pair.

When to use it

Modular inverses (RSA, hashing), solving ax + by = c, the Chinese Remainder Theorem.