XIII Международная студенческая научная конференция Студенческий научный форум - 2021

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

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

Теорема Ламе — Количество делений, которое нужно выполнить для нахождения наибольшего общего делителя двух целых чисел, не превосходит количества цифр в меньшем числе, умноженного на пять.

Доказательство. Рассмотрим последовательность Фибоначчи 

1, 1, 2, 3, 5, 8; 13, 21, 34, 55, 89; 144, 233, 377, 610, 987; 1597,…,

в которой каждый член равен сумме двух предыдущих. (Заметим, что 1 — единственное число, которое появляется дважды; для оставшейся части доказательства последовательность {1,1,2,3,5,8} эквивалентна {1,2,3,5,8}.)

Нетрудно показать, что число членов в последовательности Фибоначчи, имеющих одинаковое количество цифр, не меньше четырех и не больше пяти. Действительно, если мы обозначим через  первый член с   цифрами, то очевидным образом выполняются неравенства

так как   есть сумма двух членов с цифрами. Точно также, поскольку

и  , имеем

Аналогичным образом получаем следующие неравенства:

Поэтому группа членов, содержащих   цифр, имеет не меньше четырех и не больше пяти элементов.

Если обозначить через   члены последовательности Фибоначчи, то число   членов, предшествующих  , не больше, чем 5 (количество цифр в  ) минус один. Поэтому количество делений, которое нужно выполнить, чтобы найти наибольший общий делитель двух последовательных членов  не превосходит количества цифр в  , умноженного на пять. Предположим теперь, что мы хотим найти наибольший общий делитель двух целых чисел   . Обозначим через  убывающую последовательность остатков, полученную по алгоритму Евклида; имеем  .Предположим, кроме того, что целое число b лежит между  . Покажем, что остатки   будут содержаться в различных интервалах, образованных членами последовательности  .

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

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

Теперь рассмотрим случай  , т.е. при каком-то делении в алгоритме Евклида мы получим   (наименьшее  ). Пусть  и  — два последовательных числа Фибоначчи, между которыми содержится   тогда

и

откуда следует, что  . Если   также меньше, чем  , то интервал   будет пустым. С другой стороны, если  , то, так как   и должно выполняться неравенства  , т.е. интервал   будет пустым. Таким образом, если частное в алгоритме Евклида отлично от единицы, то найдется хотя бы один интервал в последовательности Фибоначчи, который не будет содержать остатков, и это не восполнится интервалом с двумя остатками.

Итак, для того чтобы последовательность остатков   имела ту же длину, что и последовательность   частные во всех операциях деления должны быть равными единице, так же как и . Как и в случае последовательности Фибоначчи, где   в последовательности остатков должно быть  однако   не может равняться двум, поскольку тогда эти две последовательности были бы одинаковыми и b было бы равно  что не так.

Следовательно,   должно быть равно как минимум трем и последовательность остатков будет иметь строго меньшую длину, чем последовательность Фибоначчи.

Данная теорема принадлежит Габриелю Ламе. Благодаря его деятельности научный прогресс вышел в свое время на новую ступень эволюции. Ламе внес неоценимый вклад в развитие науки, а значит и в развитии общества в целом. Труды Габриеля Ламе коснулись и дали толчок к дальнейшему развитию таких отраслей науки, как математическая теория упругости, математическая физика, строительная и прикладная механика, теория сопротивления материалов и дифференциальная геометрия.

Список используемых источников

1. Воронина М. М. Габриэль Ламе, 1795-1870: Французский ученый — математик, механик, инженер. — Л.: Наука. Ленингр. отд-ние, 1987.

2. Тихомиров В. М. Великие математики прошлого и их великие теоремы. — 2-е изд., испр. — МЦНМО , 2003. — 16 с. 

3. Энгелер Э. Метаматематика элементарной математики. — М. :Мир, 1987.