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\):