Теорема Ламе

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

Формулировка

Пусть \(a\) и \(b\) — натуральные числа, причём \(a > b\). Обозначим через \(n\) количество шагов (делений с остатком) в алгоритме Евклида для нахождения \(\gcd(a, b)\). Тогда справедливо неравенство:

\[ n \leq 5 \cdot \log_{10} b + 1 \]

или, в более слабой форме, \(n \leq 5k\), где \(k\) — количество десятичных цифр числа \(b\). В оригинальной работе Ламе использовал более точную оценку: \(n \leq 5 \cdot \log_{10} b + 1\), что эквивалентно \(n \leq 5k + 1\) для \(b \geq 1\).

Наиболее известная и часто цитируемая формулировка теоремы Ламе гласит:

Теорема. Число шагов в алгоритме Евклида для вычисления наибольшего общего делителя двух чисел не превосходит числа, равного утроенному количеству десятичных цифр меньшего из чисел, умноженному на константу. В частности, для \(b \geq 1\):

\[ n \leq 5 \cdot \log_{10} b + 1. \]

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

История

Теорема была доказана Габриэлем Ламе (1795–1870), французским математиком и инженером, известным своими работами в области теории чисел, математической физики и геометрии. Ламе опубликовал результат в 1844 году в статье «Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers» (Заметка о пределе числа делений при поиске наибольшего общего делителя двух целых чисел). Это была одна из первых работ, в которой устанавливалась связь между алгоритмической сложностью и числами Фибоначчи. Теорема Ламе считается одним из ранних примеров анализа алгоритмов — области, получившей развитие лишь в XX веке.

Доказательство

Доказательство теоремы Ламе опирается на свойства чисел Фибоначчи. Пусть алгоритм Евклида для чисел \(a\) и \(b\) (\(a > b\)) выполняется за \(n\) шагов. На каждом шаге выполняются деления с остатком:

\[ \begin{aligned} a &= q_1 b + r_1, \quad 0 < r_1 < b, \\ b &= q_2 r_1 + r_2, \quad 0 < r_2 < r_1, \\ r_1 &= q_3 r_2 + r_3, \quad 0 < r_3 < r_2, \\ &\vdots \\ r_{n-2} &= q_n r_{n-1} + r_n, \quad r_n = 0, \end{aligned} \]

где \(r_{n-1}\) — наибольший общий делитель. Важно, что на каждом шаге частное \(q_i \geq 1\), а на последнем шаге \(q_n \geq 2\), так как иначе процесс завершился бы раньше.

Из этих соотношений можно вывести, что остатки \(r_i\) убывают по крайней мере так же быстро, как числа Фибоначчи. В частности, если \(n\) шагов, то \(b \geq F_{n+1}\), где \(F_{n+1}\) — \((n+1)\)-е число Фибоначчи. Известно, что \(F_{n+1} \geq \varphi^{n-1} / \sqrt{5}\), где \(\varphi = (1+\sqrt{5})/2 \approx 1.618\) — золотое сечение. Логарифмируя, получаем:

\[ n \leq \frac{\log_{10} b + \log_{10} \sqrt{5}}{\log_{10} \varphi} + 1. \]

Поскольку \(\log_{10} \varphi \approx 0.208987\) и \(\log_{10} \sqrt{5} \approx 0.349485\), то:

\[ n \leq \frac{\log_{10} b + 0.349485}{0.208987} + 1 \approx 4.78497 \cdot \log_{10} b + 2.672. \]

Округление до целых даёт оценку \(n \leq 5 \cdot \log_{10} b + 1\). Для десятичных цифр: если \(b\) имеет \(k\) цифр, то \(\log_{10} b < k\), откуда \(n \leq 5k\).

Связь с числами Фибоначчи

Теорема Ламе показывает, что наихудший случай для алгоритма Евклида достигается на последовательных числах Фибоначчи. Например, для \(a = F_{n+2}\) и \(b = F_{n+1}\) алгоритм Евклида требует ровно \(n\) шагов. Это связано с тем, что в алгоритме для таких чисел все частные равны 1, кроме последнего, равного 2. Таким образом, числа Фибоначчи дают максимальное количество шагов при заданном размере меньшего числа.

Значение и применение

Теорема Ламе имеет важное значение в теории алгоритмов и вычислительной математике:

• Оценка сложности алгоритма Евклида. Теорема показывает, что алгоритм Евклида является полиномиальным по времени: количество шагов растёт линейно с количеством цифр входных чисел, а не с их величиной. Это делает алгоритм эффективным даже для очень больших чисел (например, с тысячами цифр).
• Анализ алгоритмов. Теорема Ламе считается одним из первых результатов в области анализа алгоритмов, предвосхитивших современную теорию сложности вычислений.
• Практические вычисления. В криптографии, где часто используются большие целые числа (например, в RSA), алгоритм Евклида применяется для нахождения обратных элементов по модулю. Теорема Ламе гарантирует, что время выполнения будет приемлемым.
• Образовательное значение. Теорема часто приводится в учебниках по дискретной математике и теории чисел как пример связи между алгоритмами и последовательностями.

Примеры

Пример 1: Наихудший случай

Рассмотрим числа Фибоначчи \(F_7 = 13\) и \(F_8 = 21\). Алгоритм Евклида:

\[ \begin{aligned} 21 &= 1 \cdot 13 + 8, \\ 13 &= 1 \cdot 8 + 5, \\ 8 &= 1 \cdot 5 + 3, \\ 5 &= 1 \cdot 3 + 2, \\ 3 &= 1 \cdot 2 + 1, \\ 2 &= 2 \cdot 1 + 0. \end{aligned} \]

Количество шагов \(n = 6\). Меньшее число \(b = 13\) имеет \(k = 2\) цифры. Оценка Ламе: \(n \leq 5 \cdot 2 = 10\). Фактическое число шагов (6) меньше границы.

Пример 2: Случайные числа

Для \(a = 123456789\) и \(b = 987654321\) алгоритм Евклида выполняется за 4 шага. Меньшее число \(b\) имеет 9 цифр, оценка Ламе: \(n \leq 5 \cdot 9 = 45\). Реальное число шагов значительно меньше.

Критика и ограничения

Теорема Ламе даёт верхнюю оценку, которая в большинстве случаев является завышенной. Для случайных чисел среднее число шагов алгоритма Евклида значительно меньше — порядка \(O(\log b)\) с коэффициентом около 1.94. Кроме того, оценка основана на десятичной системе счисления; при использовании других систем счисления (например, двоичной) константа меняется, но суть остаётся: число шагов пропорционально логарифму меньшего числа.

Интересные факты

• Теорема Ламе была опубликована в 1844 году, за 12 лет до рождения Анри Пуанкаре и за 50 лет до появления формального анализа алгоритмов.
• Числа Фибоначчи, использованные в доказательстве, были известны ещё с XIII века, но их связь с алгоритмом Евклида впервые установил Ламе.
• Теорема Ламе иногда называется «теоремой Ламе — Эйлера», так как Леонард Эйлер ранее изучал свойства алгоритма Евклида, но не дал точной оценки.

Источники

• Ламе, Г. «Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers». Comptes Rendus des Séances de l'Académie des Sciences, 1844.
• Кнут, Д. Э. «Искусство программирования», том 2: «Получисленные алгоритмы». — М.: Вильямс, 2007. — Глава 4.5.3.
• Виноградов, И. М. «Основы теории чисел». — М.: Наука, 1972. — Глава 1.
• Шенфилд, Л. «Теория чисел». — М.: Мир, 1975. — Глава 2.