Главная » Файлы » Математика » Математика |
Пусть n ∈ N , и пусть a > b > 0 такие,
31.10.2013, 17:29 | |
Теорема (Ламэ, 1845 г.). Пусть n ∈ N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = Φ n +2 , b = Φ n +1 , где Φ k - k- ое число Фибоначчи. Доказательство. Разложим a / b в цепную дробь: a ( q 1 q 2 ... q n ) , --- = ------------------------- b ( q 2 q 3 ... q n ) где q 1 , q 2 ,..., q n - неполные частные из алгоритма Евклида; по условию теоремы, их точно n штук. Согласно свойству 3 пункта 9, континуанты ( q 1 q 2 ... q n ) и ( q 2 q 3 ... q n ) взаимно просты, значит, если ( a , b ) = d - наибольший общий делитель, то Заметим, что по смыслу конечной цепной дроби, q n ≥ 2, a q 1 , q 2 ,..., q n -1 , d ≥ 1. Поскольку континуанта суть многочлен с неотрицательными коэффициентами от всех этих переменных, минимальное значение достигается при q 1 = q 2 =...= q n -1 = d = 1, q n = 2. Подставляя эти значения в получим: а = Φ n +2 , b = Φ n +1 | |
Просмотров: 319 | Загрузок: 0 | |
Всего комментариев: 0 | |
Категории раздела
Математика [249] |
Алгебра [136] |
Геометрия [416] |
Тригонометрия [109] |
Задачи по теории вероятности [60] |
Нестандартные задачи по Математике [232] |
Задачи по комбинаторике [168] |
Элементы математического анализа [51] |
Смеси,Растворы , Сплавы.Проценты , Прогрессии ,Пропорции,Движение и работа [133] |
Решение уравнений [190] |
Функция и Графики [110] |
Задачи на доказательство [151] |
Задачи с параметрами [140] |
Kоординаты и векторы [7] |
Решение неравенств [229] |
Разные решения одной задачи_ Одно решение разных задач [56] |
Контрольные задачи по темам [12] |
Формулы ,Таблицы, Правила, Теоремы [151] |
Тесты [72] |
Программирование [27] |
Высшая Математика [77] |
Теория графов [47] |
Контрольные и самостоятельные работы пр Геометрии [344] |
Друзья сайта