Extends [[Euclid's Algorithm]] to give [[Bézout's lemma|Bézout coefficients]]. > [!NOTE] Definition (Extended Euclidean Algorithm) > **Input**: Two [[Natural Numbers|natural numbers]] $a, b \in \mathbb{N}$ with $a >b>0,$ > >**Output**: The [[Greatest Common Divisor (GCD)|gcd]] of $a$ and $b$; and integers $x,y$ so that $ax+by=\gcd(a,b).$ > >**Procedure**: Finally, we have that $r_{k+1}=r_{k-1}-qk+1r_{k}$so $r_{k+1}$ is a linear combination of $r_{k+1}$ and $r_{k}$. Assume there exists $x,y\in \mathbb{Z}$ such that$\begin{align*} r_{k+1}&=xr_{k-t}+yr_{k-t+1}\\ \text{then } r_{k-t-1}&=q_{k-t-1}r_{k-t}+r_{k-t+1}\\ \text{so } r_{k-t+1}&=r_{k-t-1} - q_{k-t-1}r_{k-t}\\ \text{giving } r_{k+1} &= xr_{k-t}+y[r_{k-t-1}-q_{k-1}r_{k-t}]\end{align*}$Which is equal to$ [x-yq_{k-t+1}]r_{k-t}+yr_{k-t-1}$the bit in the square brackets is just an integer so $r_{k+1}$ is a linear combination of $r_{k-t}$ and $r_{k-t-1}$, so by mathematical induction, we can write $r_{k+1}$ as a linear combination of any consecutive pair of remainders. In particular $\gcd(a,b)=r_{k+1}$ is a linear combination of $a$ and $b$. # Applications **Solving systems of linear congruences**: The [[Chinese remainder theorem|Chinese remainder theorem]] asserts that there is a unique solution to any system of linear congruences provided the moduli are pairwise coprime. The main idea is that given $\gcd(a,b)=1,$ we can can find a unique solution to $bx\equiv 1 \pmod{a}$ using the above algorithm.