Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Здесь мы опишем алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел $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)$.
