Здесь мы опишем алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел $n_{0} \geqslant n_{1}$ [38]. Алгоритм осуществляется как последовательное деление с остатком следующих чисел:
\[
\begin{array}{c}
n_{0}=d_{1} \times n_{1}+n_{2} \\
n_{1}=d_{2} \times n_{2}+n_{3} \\
\cdots \\
n_{m-2}=d_{m-1} \times n_{m-1}+n_{m} \\
n_{m-1}=d_{m} \times n_{m}+0,
\end{array}
\]

где $d_{m}$ — частные и $n_{m-1} \geqslant n_{m}$ на каждом шаге. Последний ненулевой остаток $n_{m}$ дает ответ, т. е. НОД $\left(n_{0}, n_{1}\right)=n_{m}$. Например, последовательность делений
\[
\begin{array}{l}
91=3 \times 28+7 \\
28=4 \times 7+0,
\end{array}
\]

дает НОД $(28,91)=7$ прямо за два шага. В худшем случае число шагов, требуемых для выполнения алгоритма Евклида, равно $O\left(\log \log n_{1}\right)$.