HI WORLD

I love cp algorithms articles but sometimes there are some proofnesses that I can't figure out by myself. I've just checked the proofness of transition of coefficients in extended euclidian algorithm and I'd like to share my explanation here.

Given $$$a$$$ and $$$b$$$, we need to calculate $$$x$$$ and $$$y$$$ such that satisfies Bézout's identity: $$$ax + by = gcd(a,b)$$$.

Starting with values $$$x=1$$$, $$$y=0$$$, $$$x_1=0$$$, $$$y_1=1$$$, $$$a_1=a$$$, $$$b_1=b$$$, after some iterations $$$b_1$$$ will become $$$0$$$ and $$$a_1$$$ will become $$$gcd(a,b)$$$:

// by cp algorithms
int gcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

We have these transitions:

$$$-$$$

$$$-$$$

The third transition is very clear. It's explained in the previous chapter about the normal Euclidean algorithm. But what is the reason that the first two transitions are correct as well?

At the beginnig we have these equalities:

• $$$ax + by = a_1$$$
• $$$ax_1 + by_1 = b_1$$$

On the following transition we'll have:

• $$$ax_1 + by_1 = b_1$$$
• $$$ax_2 + by_2 = a_1\%b_1 = a_1 - (a_1/b_1)*b_1 = a_1 - qb_1$$$

Replacing values of $$$a_1$$$ and $$$b_1$$$ on last equation we have:

Rearranging:

By comparinson we have:

• $$$x_2 = x - x_1q$$$
• $$$y_2 = y - y_1q$$$

$$$x_2$$$ and $$$y_2$$$ are just the next values of x1 and y1. So we have checked the proofness of transition of coefficients of extended euclidean algorithm, iterative version.

Any observations will be really helpful. Thanks for reading ^-^