Задача 60592

Темы:    [ Алгоритм Евклида ] [ Числа Фибоначчи ]

Сложность: 4- Классы: 9,10,11 Название задачи: Теорема Ламе.

Условие

Пусть число m₁ в десятичной системе счисления записывается при помощи n цифр.
Докажите, что при любом m₀ число шагов k в алгоритме Евклида для чисел m₀ и m₁ удовлетворяет неравенству  k ≤ 5n.

Подсказка

См. задачи 60591 и 60590 б).

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	4
Название	О том, как размножаются кролики
Тема	Классическая комбинаторика
задача
Номер	03.140