7.3. Алгоритмы деления и алгоритм евклида

Ранее была доказана теорема, названная алгоритмом деления. Теорема гласила, что для положительных целых чисел а и b существуют единственные неотрица­тельные числа q и r такие, что 0 < r < b и а = bq+r. Это утверждение не является алгоритмом, но алгоритмы для нахождения q и r существуют. Если числа а и b велики, число q можно “угадать". Если умножить b на q и результат слишком велик, следует q заменить на q - 1 и повторять процесс, пока не получим bq < а, после чего положить r = а - bq. Однако, если bq < а, но а - bq > b, то следует заменить q на q + 1 и повторять процесс, пока не получим a-bq < b, после чего положить r = a-bq. Более системно метод описывается следующим образом:

1) Положить q = 1 и r = а - bq.

2) Если r ≥ b, положить q = q + 1 и r = а - bq.

3) Продолжать процесс, пока r < b.

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

ТЕОРЕМА 7.2. (Алгоритм Евклида) Допустим, что а и b — положительные целые числа, и последовательное применение алгоритма деления приводит к по­следовательности следующего вида:

Существует r_к = 0. Пусть s — первое целое число такое, что r_s = 0. Тогда r_s-1 = НОД(а,b), если s > 0, и b = НОД(а.b), если s = 0.

ДОКАЗАТЕЛЬСТВО. Пусть S = {r₀, r₁ ,...}. Если r₀ = 0, тогда результат очеви­ден, поэтому предположим, что r₀ > 0. Согласно принципу полного упорядочения множество S содержит наименьшее положительное целое число, скажем, r_i. Но 0≤ r_i+1 < r_i и поэтому r_i+1 = 0. Положим s = i + 1.

По теореме 3.33,

ПРИМЕР 7.3. Используя алгоритм Евклида для нахождения НОД(203,91), дей­ствуем следующим образом. Сначала делим 203 на 91 нацело и получаем

Теперь делим 91 на остаток 21 нацело:

Разделяя 21 на 7 нацело, получаем

Алгоритм Евклида позволяет находить такие значения u и v, что НОД(а, b) = r_t, au + vb = НОД(а,b). Используя обозначения теоремы 7.2, запишем r_t-2 = r_t-1• q_t + r_t. Отсюда r_t = r_t-2 – r_t-1 • q_t. Аналогично, r_t-1 = r_t-3 - r_t-2 • q_t-1. Подстановка в предыдущее уравнение дает

Аналогичным образом можно выразить r_t-2 через r_t-3 и r_t-4 и, подставив в пре­дыдущее уравнение, исключить r_t-2. Продолжая в том же духе, можно исключить все n и вернуться обратно к а и b, получив НОД(а. b) в виде uа + vb.

ПРИМЕР 7.7. Выразить НОД(252,576) в виде 252u + 576u. Сначала разделим 576 на 252 нацело:

576 = 252 • 2 + 72.

Теперь разделим 252 нацело на 72:

252 = 72 • 3 + 36.

После обратной подстановки получаем

36 = 252-72-3 =

= 252 - [576 - 252 • 2] • 3 =

= (7)(252) + (—3)(57б). □

В примере 7.3 показано, что НОД(91,203) = 7. Если разделить числа 91 и 203 на их наибольший общий делитель 7, получим 91/7 = 13 и 203/7 = 29. Легко видеть, что целые числа 13 и 29 — взаимно простые; т.е. НОД(13,29) = 1. Таким образом, оказалось, что результаты деления двух целых чисел на их наибольший общий делитель не имеют общих делителей, за исключением 1. Доказательство следующей теоремы предоставляем читателю.

ТЕОРЕМА 7.8. Пусть заданы целые числа а и b, не равные нулю, тогда числа a/НОД(a.b) и b/НОД(a.b) являются взаимно простыми, т.е. НОД (a/НОД(a.b) , b/НОД(a.b)) = 1.

Было определено ранее, что положительное целое число т представляет собой наименьшее общее кратное целых чисел а и b при условии, что (а) а | m и b | m, и (б) если n — любое общее кратное чисел а и b, то m | n. Наименьшее общее кратное чисел а и b обозначим НОК(а,6).

Необходимо построить алгоритм нахождения наименьшего общего кратного двух целых чисел. Цель достигается определением наибольшего общего делителя этих чисел (алгоритм нахождения которого уже имеется) и использованием тео­ремы 3.50. Указанная теорема утверждает, что для положительных целых чисел а и b НОД(а, b) • НОК(а, b) = аb.

Для нахождения НОК(91,203) сначала определим НОД(91,203), воспользо­вавшись алгоритмом Евклида, как это было сделано ранее, а затем разделим на него произведение чисел 91 и 203. Поскольку НОД(91,203) = 7, находим