Таблицы Брадиса

Тогда получается, что пара, полученная

Тогда получается, что пара, полученная

Элементы математики в задачах - Г. А. Мерзон

а) НОД(91,147); б) НОД(—144, —233).

Решение. а) НОД(91,147) = НОД(147, 91). Распишем для последней пары алгоритм Евклида: (147, 91) ^ (91, 56) ^ (56, 35) ^ (35, 21) ^ ^ (21,14) ^ (14, 7) ^ (7, 0). Значит, НОД(91,147) = 7.

б) НОД(—144, —233) = НОД(233,144). Распишем для послед­ней пары алгоритм Евклида: (233,144) ^ (144, 89) ^ (89, 55) ^ ^ (55, 34) ^ (34, 21) ^ (21,13) ^ (13, 8) ^ (8, 5) ^ (5, 3) ^ (3, 2) ^ ^ (2,1) ^ (1, 0). Значит, НОД(—144, —233) = 1.

166                      Целые числа 2. Алгоритм Евклида

Задача 10. Пусть 0 < а < 1000, 0 < Ъ < 1000. Верно ли, что алгоритм Евклида закончится после не более, чем а) 14; б) 13 шагов?

Решение. Рассмотрим следующую последовательность пар алгоритма Евклида, записанную в обратном порядке: (1, 0) ^ (2,1) ^ (3, 2) ^ ^ (5,3) ^ (8,5) ^ (13,8) ^ (21,13) ^ (34,21) ^ (55,34) ^ (89,55) ^ ^ (144, 89) ^ (233,144) ^ (377, 233) ^ (610, 377) ^ (987, 610). (*)

Если обратить эту последовательность, то мы получим алгоритм Евклида, который заканчивается после 14 шагов (таким образом, ответ на второй вопрос задачи отрицательный).

Будем говорить что пара (а, Ъ) «не меньше» пары (с, й), если а ^ с и Ъ ^ й. Теперь предположим, что нам удалось найти такие а и Ъ, по мо­дулю меньшие тысячи, что алгоритм Евклида для них заканчивается более чем через 14 шагов. Запишем его «задом наперед» и обозначим (**). Докажем, что для каждого номера і будет выполняться следу­ющее: і-я скобка (**) «не меньше» і-й скобки (*). Доказательство проведем по индукции.

База индукции: первая пара (**) имеет вид (й, 0), а значит, она не меньше пары (1, 0).

Шаг индукции: Пусть некоторая і-я пара (т, п) последовательно­сти (**) не меньше пары (к, I) последовательности (*). Тогда пара (т + п, т), которая следует после пары (т, п) в (**), не меньше пары (к +1, к), которая следует после пары (к, I) в (*).

Тогда получается, что пара, полученная после 15 шагов алгоритма (**), будет не меньше пары (1597,987), но это противоречит тому, что и а и Ъ меньше 1000.