# Euclidean Algorithm
**An efficient method of computing the [[greatest common divisor]] of two integers.**
The **Euclidean algorithm** consists of a series of steps with the output of each step substituted as the input of the next.
If each step is labelled as $k$, then every step uses two *non-negative inputs* $r_{k-2}$ and $r_{k-1}$ with $r_{k-2}>r_{k-1}$. The $k$th step involves Euclidean division and, by the [[division theorem]],
$r_{k-2}=q_{k}r_{k-1}+r_{k},\quad r_{k-1}>r_{k}\ge 0$
If the GCD of numbers $a$ and $b$ is to be found, then for the initial step $k=0$ the inputs are $r_{-2}=a$ and $r_{-1}=b$.
The algorithm proceeds as follows:
$\begin{gather}
a=q_{0}\times b+r_{0} \\
b=q_{1}\times r_{0}+r_{1} \\
r_{0}=q_{2}\times r_{1}+r_{2} \\
r_{1}=q_{3}\times r_{2}+r_{3} \\
\vdots \\
r_{n-2}=q_{n}\times r_{n-1}+r_{n} \\
r_{n-1}=q_{n+1}\times r_{n}+0
\end{gather}$
As the remainders for non-negatives integers will decrease for every step, the sequence $r_{-1}>r_{0}>r_{1}>\dots\ge 0$ must eventually terminate.
The second last step of the process, the $n$th step, outputs a remainder equal to the GCD of $a$ and $b$.
$\gcd(a,b)=r_{n}$
After applying the Euclidean algorithm to find $\gcd(a,b)$, it can be *reversed* to find integer solutions for [[Bézout’s identity]].
>[!Example]- Example - Euclidean algorithm
>To find $\gcd(403,286)$,
>$\begin{gather}
>403 = 1\times 286+117 \\
>286 = 2\times 117+52 \\
>117 = 2\times 52+\underline{13} \\
>52 = 4\times 13+0
>\end{gather}$
>Thus, $\gcd(403,286)=13$.
>[!Example]- Example - Reverse Euclidean algorithm
> To find integers $x$ and $y$ such that $\gcd(403,286)=13=403x+286y$, rearrange the *penultimate* step of the Euclidean algorithm from the previous example.
> $\begin{align*}
> 13&=117-2\times 52 \\
> &=117-2(286-2\times 117) & \text{substitution from 2nd line}\\
> &=5\times 117-2\times 286 & \text{collecting terms} \\
> &=5\times(403-286)-2\times 286 & \text{substitution from 1st line} \\
> &=5\times 403-7\times 286
> \end{align*}$
> Thus, $x=5$ and $y=-7$ is a solution to $13=403x+286y$