# Extended Euclidean algorithm calculator

Given two integers $$a$$ and $$b$$, the extended Euclidean algorithm computes integers $$x$$ and $$y$$ such that $$ax + by = gcd(a,b)$$.

The algorithm computes a sequence of integers $$r_1 > r_2 > \ldots > r_m$$ such that $$gcd(a,b)$$ divides $$r_i$$ for all $$i = 1,\ldots,m$$ using the classic Euclidean algorithm. At iteration $$i$$, the algorithm computes $$r_i$$ and integers $$x_i$$ and $$y_i$$ such that $$ax_i + by_i = r_i$$. The algorithm terminates when $$r_i = gcd(a,b)$$.

We initialize the algorithm with $$r_1 = a, r_2 = b, x_1 = 1, x_2 = 0, y_1 = 0, y_2 = 1$$ Then starting from iteration $$i = 3$$, we compute $$r_i$$ as

$$r_i = r_{i-2} - \lfloor r_{i-2}/r_{i-1} \rfloor r_{i-1}$$

Since $$gcd(a,b)$$ divides both $$r_{i-2}$$ and $$r_{i-1}$$, it also divides $$r_i$$. Now we plug in $$r_{i-1} = a x_{i-1} + b y_{i-1}$$ and $$r_{i-2} = a x_{i-2} + b y_{i-2}$$. We get:

$$r_i = (a x_{i-2} + b y_{i-2}) - \lfloor r_{i-2}/r_{i-1} \rfloor (a x_{i-1} + b y_{i-1})$$

Rearranging:

$$r_i = (x_{i-2} - \lfloor r_{i-2}/r_{i-1} \rfloor x_{i-1}) a + (y_{i-2} - \lfloor r_{i-2}/r_{i-1} \rfloor y_{i-1}) b$$

We have found: $$x_i = (x_{i-2} - \lfloor r_{i-2}/r_{i-1} \rfloor x_{i-1}), y_i = (y_{i-2} - \lfloor r_{i-2}/r_{i-1} \rfloor y_{i-1})$$, which completes the iteration. The algorithm is iterated until $$r_i = gcd(a,b)$$.

$$a$$: $$b$$: