Extended Euclidean Algorithm

Extended Euclid computes the GCD together with integers x,y satisfying a·x+b·y=gcd(a,b). This is Bézout’s identity: the smallest positive integer expressible as such an integer linear combination is the GCD. These coefficients turn a divisor calculation into a constructive tool for modular inverses and integer equations. We derive the recursive update directly from the ordinary Euclidean remainder step.

Prerequisites: GCD; recursion; signed arithmetic.

Build the idea

1. 1. Understand what a coefficient certificate means

   For a=30,b=18,g=6, x=−1,y=2 is valid because −30+36=6. Coefficients may be negative even when inputs are positive. They are not divisors or remainders, and the pair is generally not unique. The algorithm needs one valid pair, not the smallest absolute coefficients.

   $$\mathrm{ax}+\mathrm{by}=\gcd (a,b)$$

2. 2. Start at a simple base

   When b=0 and a>0, gcd(a,0)=a, so x=1,y=0 works. If both a and b are zero, this implementation returns g=0 with the same coefficients, a valid equality 0=0 but not a positive-GCD statement. The program does not divide by this result.

3. 3. Substitute the smaller equation

   The recursive call gives b·x₁+(a mod b)·y₁=g. Replace a mod b by a−floor(a/b)·b for our nonnegative inputs. Collect coefficients to get a·y₁+b·(x₁−floor(a/b)·y₁)=g. Therefore x=y₁ and y=x₁−(a/b)·y₁. This algebra is the entire coefficient update; swapping x and y without the subtraction would be wrong.

   $$x=y\mathrm{₁},y=x\mathrm{₁}-\mathrm{qy}\mathrm{₁}$$

4. 4. Trace 30 and 18

   Euclid descends through (30,18),(18,12),(12,6),(6,0). The base coefficients (1,0) lift to (0,1), then (1,−1), then (−1,2). Checking the original equation gives 30·(−1)+18·2=6. The program prints g,x,y and recomputes the left-hand side as an explicit certificate.

   Pair	x	y
   6,0	1	0
   12,6	0	1
   18,12	1	-1
   30,18	-1	2

5. 5. Connect the identity to later algorithms

   If g=1, reducing ax+by=1 modulo b makes ax≡1, so x is an inverse of a modulo b when b>1. For ax+by=c, solutions require g dividing c and coefficients can then be scaled by c/g. The next lessons normalize signs and limit products explicitly instead of assuming any scaling always fits.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
using ll=long long;
ll extended(ll a,ll b,ll&x,ll&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1,y1,g=extended(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1; // Substitute the smaller equation back into a,b.
    return g;
}
int main(){
    ll a,b,x,y;
    std::cin>>a>>b;
    ll g=extended(a,b,x,y);
    std::cout<<g<<' '<<x<<' '<<y<<'\n';
    std::cout<<a*x+b*y<<'\n'; // Certificate, safe under this lesson's bounds.
}

Complexity analysis

O(log(max(a,b)+1)) arithmetic operations and recursion depth. O(log(max(a,b)+1)) stack memory. The coefficient update is constant work per Euclidean step. Input bounds a,b≤10^9 keep coefficient products and the displayed certificate safely within long long.

Example input and output

Read a b in 0..10^9. Print g x y with ax+by=g, then the recomputed left-hand side. Any valid coefficient pair may differ from this implementation’s deterministic output.

Input

30 18

Output

6 -1 2
6

The recursive substitution yields −1 and 2; −30+36=6.

Practical applications

Use for inverse computation under any modulus with a coprime operand, constructing Diophantine solutions and generalized CRT merges. Plain std::gcd is simpler when only the divisor is needed. The returned identity is a useful implementation test: verify both the GCD and the coefficient equation.

Check your understanding

Which coefficients lift b·x₁+(a mod b)·y₁=g to a,b?

Put it into practice

Check the identity for random small pairs and swapped inputs.