Extended Euclidean Algorithm

C++

1ll euclid(ll a, ll b) {
2    for (;b;swap(a,b)) {
3        ll k = a/b;
4        a -= k*b;
5    }
6    return a; // gcd(a,b)
7}

Extended Euclidean Algorithm

The extended Euclidean algorithm computes integers $x$ and $y$ such that

C++

1array<ll,3> extendEuclid(ll a, ll b) {
2    array<ll,3> x = {1,0,a}, y = {0,1,b};
3    // we know that 1*a+0*b=a and 0*a+1*b=b
4    for (;y[2];swap(x,y)) { // run extended Euclidean algo
5        ll k = x[2]/y[2];
6        F0R(i,3) x[i] -= k*y[i];
7        // keep subtracting multiple of one equation from the other
8    }
9    return x; // x[0]*a+x[1]*b=x[2], x[2]=gcd(a,b)
10}

C++

1ll euclid(ll a, ll b) {
2    if (!b) return a;
3    return euclid(b,a%b);
4}

C++

1pl extendEuclid(ll a, ll b) { // returns {x,y}
2    if (!b) return {1,0};
3    pl p = extendEuclid(b,a%b); return {p.s,p.f-a/b*p.s};
4}

C++

1ll invGeneral(ll a, ll b) {
2    array<ll,3> x = extendEuclid(a,b);
3    assert(x[2] == 1); // gcd must be 1
4    return x[0]+(x[0]<0)*b;
5}
6
7int main() {
8    FOR(b,1,101) F0R(a,101) if (__gcd(a,b) == 1) {
9        ll x = invGeneral(a,b);
10        assert((a*x-1)%b == 0);