Евклида алгоритм

Определение

Вообще говоря, остановится он гораздо быстрее (подумайте, почему?), а примером самого медленного схождения является отыскание с его помощью наибольшего общего делителя у двух соседних чисел последовательности Фибоначчи.
Кстати, попробуйте и так доказать, что такие два числа обязаны быть взаимно просты.

Алгоритм Евклида – алгоритм для нахождения наибольшего общего делителя двух целых чисел a и b (общей меры двух целочисленных величин), впервые описанный древнегреческим математиком Евклидом в «Началах» (III в. до н. э.) – своем главном труде, посвященном геометрии и теории чисел.

Идея алгоритма состоит в том, что мы пытаемся «исчерпать» меньшей величиной
(пускай это будет число b) большую – меньшая, скорее всего, уложится в большей некоторое целое число раз с каким-то остатком, величина которого строго меньше
той величины, которой мы черпали.

Ну это и понятно – если бы она была «нестрого меньше», то мы смогли бы ее зачерпнуть еще один полный раз. Затем мы уменьшаем «кандидата» на общую меру, черпая теперь уже величиной остатка. Поскольку оба числа у нас по условию целые, то в худшем случае такой общей мерой будет единица – тогда говорят, что числа a и b взаимно просты, или что НОД (a, b) = 1 – иначе НОД (a, b) будет равен последнему ненулевому остатку в организованной таким образом процедуре.

Следовательно, алгоритм гарантированно останавливается не позднее, чем через b шагов.

Все, что нам нужно, так это

В общем случае всякое целое а единственным способом представимо через положительное целое b в виде:

a = bq + r, 0 ≤ r < b

Число q в этом случае называется неполным частным,
а r – остатком от деления а на b;

Если а кратно b, то множество
общих делителей чисел а и b, совпадает
с множеством делителей одного b.
В частности, (а, b) = b.

Понятно также, что наибольшим делителем b будет само b. Поэтому (а, b) = b.

Нами уже была проделана вся подготовительная работа, необходимая для изложения недостающих формальных оснований того, как работает алгоритм Евклида (прочитать можно здесь).

Если a = bq + с, то множество общих делителей а и b совпадает с множеством общих делителей b и с.
В частности, (а, b) = (b, с).

1 свойство

2 свойство

– и следующие два свойства наибольшего общего делителя двух целых чисел a и b, который ниже бы будет обозначать просто как (a, b):

– теорема о делении с остатком:

заканчивающийся, когда получим некоторое

Значит, если нам даны два положительных целых
a и b, мы всегда можем подобрать ряд равенств

Последнее, как мы уже отмечали, неизбежно, так как
по построению мы имеем последовательность строго убывающих положительных целых

которых не может

Далее мы видим, что общие делители чисел a и b совпадают (свойство 2) с общими делителями

быть больше b штук.

которых не может быть больше b штук.

То есть совокупность множества общих делителей чисел a и b совпадает
с совокупностью делителей их наибольшего общего делителя, который равен
r – последнему ненулевому остатку в алгоритме Евклида.

Имеем

Написать в чат

Есть вопросы по материалу?

Вы можете задать их в нашем специальном чате. Мы поможем разобраться в теме лучше

Понравилась статья?