> [!NOTE] Definition (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.$ > > **Procedure**: Repeatedly, using [[Division with remainder for integers|division with remainder]] we can write$\begin{align} a & =q_{1}b+r_{1} &\mathrm{where}~b>r_{1}\geq0 \\ b&=q_{2}r_{1}+r_{2} &\mathrm{~where~}r_{1}>r_{2}\geq0 \\ r_{1}&=q_{3}r_{2}+r_{3} &\mathrm{where }\,r_{2}>r_{1}\geq0 \end{align}$ and in general, $r_{t}=q_{t+2}r_{t+1}+r_{t+2}$ while $r_{t+1}>r_{t+2}\geq0.$ > # Properties **Correctness**: First note [[Finiteness and Validity of Euclid's Algorithm]]. **Runtime**: > [!NOTE] Proposition (Runtime) > Contents # Properties **Visualisation**: [[Geometrical Interpretation of Euclid's Algorithm]]. **Implementation**: See [[Euclid's Algorithm Implementation in Python|pythonic implementation]]. # Application **Bézout's lemma**: The [[Extended Euclidean Algorithm|extended Euclidean algorithm]] can be used to compute [[Bézout's lemma|Bézout coefficients]] of two integers (i.e two integers $x$ and $y$ so that $ax+by=\gcd(a,b)$). **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.