Материалы по подписке
Алгоритм
Евклида
Определение
Алгоритм Евклида алгоритм для нахождения наибольшего общего делителя двух целых чисел a и b (общей меры двух целочисленных величин), впервые описанный древнегреческим математиком Евклидом в «Началах» (III в. до н. э.) – своем главном труде, посвященном геометрии и теории чисел.
Идея алгоритма состоит в том, что мы пытаемся «исчерпать» меньшей величиной (пускай это будет число b) большую – меньшая, скорее всего, уложится в большей некоторое целое число раз с каким-то остатком, величина которого строго меньше той величины, которой мы черпали. Ну это и понятно – если бы она была «нестрого меньше», то мы смогли бы ее зачерпнуть еще один полный раз. Затем мы уменьшаем «кандидата» на общую меру, черпая теперь уже величиной остатка. Поскольку оба числа у нас по условию целые, то в худшем случае такой общей мерой будет единица – тогда говорят, что числа a и b взаимно просты, или что НОД (ab) = 1 – иначе НОД (ab) будет равен последнему ненулевому остатку в организованной таким образом процедуре.
Заметка
Следовательно, алгоритм гарантированно останавливается не позднее, чем через b шагов. Вообще говоря, остановится он гораздо быстрее.
А примером самого медленного схождения является отыскание с его помощью наибольшего общего делителя у двух соседних чисел последовательности Фибоначчи.
!
Подумайте, почему
Про последовательность Фибоначчи можно прочитать здесь:
Пост «Божественная суть» размножения кроликов
Кстати, попробуйте и так доказать, что такие два числа обязаны быть взаимно просты.
Нами уже была проделана вся подготовительная работа, необходимая для изложения недостающих формальных оснований того, как работает алгоритм Евклида. Посмотреть можно здесь:
Статья «Введение в теорию чисел. Основная теорема арифметики»
Все, что нам нужно, так это – теорема о делении с остатком:
В общем случае всякое
целое а единственным способом представимо через положительное целое b в виде:
Число q в этом случае называется неполным частным, а r — остатком от деления а на b
a = bq + r, 0 ≤ r < b
и следующие два свойства наибольшего общего делителя двух целых чисел a и b, который ниже будем обозначать просто как (ab):
Если а кратно b, то множество общих делителей чисел а и b, совпадает с множеством делителей одного b.
В частности, (а, b) = b.
Если a = bq + с, то множество общих делителей а и b совпадает с множеством общих делителей b и с.
В частности, (а, b) = (b, с).
1 свойство
2 свойство
Значит, если нам даны два положительных целых a и b, мы всегда можем подобрать ряд равенств
a = bq₁ + r₂;
b = rq₂ + r₃;
r₂ = rq₃ + r₄;
0 < r₂ < b,
0 < r₃ < r₂,
0 < r₄ < r₃,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(1)
Последнее, как мы уже отмечали, неизбежно, так как по построению мы имеем последовательность строго убывающих положительных целых b < r₂ < r₃ <... , которых не может быть больше b штук.
Видео «Урок 2»
a = bq₁ + r₂,


b = rq₂ + r₃,


r₂ = rq₃ + r₄,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Откуда
То есть, рациональное число α всегда представимо в виде конечной цепной дроби. И это прямое следствие алгоритма Евклида, даже лучше сказать – его другая форма. И наоборот, невозможность такого представления, или напротив – доказательство того, что некоторое число β представимо лишь в виде бесконечной цепной дроби, есть строгое доказательство его иррациональности. Что, в частности, и проделал в свое время Леонард Эйлер с числом e
Заметка
Про число е вы можете прочитать здесь:
Статья «Число e (число Эйлера)»
Последний чрезвычайно важный момент, который нам хотелось бы здесь обсудить – это связь цепных дробей с соотношением Безу
Cоотношением Безу также было нами подробно разобрано и доказано в видеоуроке по теории чисел
Видеоурок «Число e (число Эйлера)»
Каковы бы ни были два натуральных числа а и b, всегда найдутся такие два натуральных числа x и y, что ax − by = (ab).
Теорема
Это соотношение еще иногда называют линейным представлением НОД (ab), или представлением наибольшего общего делителя чисел a и b в виде их линейной комбинации с целыми коэффициентами.
Но если соотношение Безу говорит просто о существовании такой линейной комбинации, то теория непрерывных дробей утверждает нечто, значительно более конструктивное.
Вернемся к уже знакомой нами записи:
Еще одно принятое обозначение:
Дроби вида
называют подходящими дробями порядка k к данной несократимой дроби
...,
Введем следующие обозначения:
Q₀ = 0,
P₀ = Q₁ = 1,
P₁ = q
Доказательство этого факта можно усмотреть непосредственно, а можно выполнить его по индукции, которая в данном случае тоже оказывается вполне наглядной:
Очевидным образом верно.
Тоже вопросов не вызывает.

А дальше заметим, что
И, значит,
Да и вообще, поскольку
то мы можем допустить, что
соответствующую замену:
Теперь уже для всех натуральных s > 1.
выполнено по индукционному предположению, и получить выражение для s, сделав в формуле для
Основная же Теорема о непрерывных дробях утверждает следующее:
Заметка
А доказательство будет совсем уже теперь простым.
Ну и заключительный микробонус:
Пост «Последовательность Фибоначчи»
Полезные материалы
Статья «Лемма Евклида»
Подтема «Соотношение Безу»
Видеоуроки по теории чисел
Статья «Число е»
Полезные материалы
Пост «Последовательность Фибоначчи»
Подтема «Соотношение Безу»
Статья «Число е»
Статья «Лемма Евклида»
Видеоуроки по теории чисел
Понравилась статья?