Extended Euclidean algorithm

The objective of the extended Euclidean algorithm is to compute the greatest common divisor of two natural numbers and solve Bézout’s identity

$ax+by=d$.

Given two positive integers a and b, this Diophantine equation is solved for integers x, y, which will not both be positive, and $d=\gcd(a,b)$.

If $d=1$, the algorithm yields the modular inverses of a mod b and b mod a since in this case the congruences

$ax\equiv 1\mod b$

and

$by\equiv 1\mod a$

are solved.

Example code

Here is a naïve C++ implementation of pseudocode found on Wikipedia.

#include <iostream>
#include <cassert>

int main(int argc, char **argv) {
    long int a, b, q, r0, r1, r,
        s0 = 1, s1, s = 0, t0 = 0, t1, t = 1;
    std::cout << "Enter two positive integers: ";
    std::cin >> a >> b;
    assert(a > 0 && b > 0); r0=a; r=b;
    while(r != 0) {
        q = r0 / r;
        r1 = r0 - q * r; r0 = r; r = r1;
        s1 = s0 - q * s; s0 = s; s = s1;
        t1 = t0 - q * t; t0 = t; t = t1;
    }
    std::cout
        << "Bézout coefficients: "
            << s0 << ", " << t0 << std::endl
        << "greatest common divisor: "
            << r0 << std::endl
        << "quotients by the gcd: "
            << t << ", "<< s << std::endl;
    return 0;
}

Using GNU multiprecision bignum classes

The long int primitive type in C++ cannot handle numbers bigger than 18,446,744,073,709,551,615 on most computers. The program above may be adapted to handle much, much bigger numbers with multiprecision arithmetic, and this is practical for actual implementations that will be highly efficient. Be sure g++, gmp, gmp++, gmp-devel are installed on your your Fedora Linux system, e.g.

$ sudo dnf install gmp gmp++ gmp-devel

Be sure you have

#include <gmpxx.h>

along with the other includes, declare the variables as mpz_class instead of long int, and link the bignum libraries when you compile , assuming here you have saved the program as e-euclid.cpp.

$ g++ -o e-euclid e-euclid.cpp -lgmpxx -lgmp
$ ./e-euclid