Вычисление нод. Алгоритм Евклида

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

Лемма 1. Если , то .

Доказательство. Очевидно, что – общий делитель чисел  и , поскольку  и . Пусть – общий делитель чисел  и , тогда . Значит,  – наибольший общий делитель чисел  и  по определению.

Лемма 2. Пусть , причем числа  и  отличны от 0 и . Тогда

Доказательство. Пусть множество общих делителей чисел  и , а  множество общих делителей чисел  и . Докажем, что .

Пусть , это значит, что  и . Тогда по свойству делимости . Тогда, , следовательно, . Аналогично докажем, что . Из определения равенства двух множеств получим, что .

Если два числовых множества совпадают, то совпадают их наибольшие по величине элементы, что и доказывает лемму.

 

Сформулируем теперь алгоритм Евклида.

Рассмотрим два целых числа  и . Пусть  Требуется найти наибольший общий делитель чисел  и .

Шаг 1. Разделим  на . Если , то по лемме 1 получим, что .

Если число  не делится на , то , где . Тогда по лемме 2

Шаг 2. Разделим  на . Если , то  (по лемме 1). Тогда .

Если  не делится на , то , где . Тогда по лемме 2 , а значит, справедливо и

Продолжая процесс деления, получим последовательность остатков – убывающую последовательность целых неотрицательных чисел, вычисляемых по следующим рекуррентным формулам: .

 Поскольку такая последовательность не может иметь бесконечно много членов, на некотором шаге очередной остаток окажется равным нулю. Тогда последний, отличный от нуля остаток и есть НОД чисел  и .

Пример. Найдем НОД чисел  и . Для этого разделим  на , получим . Таким образом, первый полученный остаток .

Далее, разделим  на , получим , при этом .

Продолжим процесс деления:

, ;

, ;

, ;

, .

Таким образом, последний отличный от  остаток равен , это и есть наибольший общий делитель чисел  и .

В следующей теореме утверждается, что наибольший общий делитель двух чисел можно представить в виде линейной комбинации этих чисел с целыми коэффициентами.

Теорема 4.1. (линейное представление НОД)

      Рассмотрим два целых числа  и . Пусть , . Тогда найдутся такие целые числа  и , что .

Доказательство. Докажем, что каждый из остатков , полученных в процессе выполнения алгоритма Евклида, можно представить в виде линейной комбинации чисел  и  с целыми коэффициентами. Тогда это утверждение будет справедливо в частности и для последнего, отличного от  остатка, равного . Будем доказывать это утверждение методом математической индукции.

База индукции.

Пусть . Имеем , тогда . Получили, что остаток  можно представить в виде линейной комбинации чисел  и  с целыми коэффициентами   и .

Индукционный переход.

Пусть утверждение справедливо для всех натуральных чисел , не превосходящих : , при . Докажем, что это утверждение справедливо также для .

Из алгоритма Евклида следует, что

.

По индукционному предположению

и . 

Следовательно, .

Положим  и . Тогда , что и требовалось установить.

Пример. В предыдущем примере был найден НОД чисел  и  : . Найдем его линейное представление:

Итак, получили, что , т. е. представили НОД чисел  и  в виде их линейной комбинации с целыми коэффициентами.

 

Взаимно простые числа

Определение 5.1. Целые числа  называются взаимно простыми, если их НОД равен :

Примеры.

1. Числа  и  – взаимно простые.

2. Числа  и  – не взаимно простые, так как .

Следующая теорема устанавливает необходимое и достаточное условие взаимной простоты чисел.

Теорема 5.1 (признак взаимной простоты чисел). Для того, чтобы числа  и  были взаимно простыми, необходимо и достаточно, чтобы нашлись такие целые числа  и , что .

Доказательство. 1. Необходимость. Пусть числа  и  взаимно просты, то есть . Тогда по теореме о линейном представлении НОД найдутся такие целые числа  и , что .

2. Достаточность. Пусть справедливо утверждение , где  и  – целые числа. Докажем, что . Предположим, что числа  и  не являются взаимно простыми: , причем . Тогда  и , и по свойству делимости . Значит, , следовательно, . Полученное противоречие доказывает, что сделанное нами предположение неверно, и, тем самым, справедливо .

Следствие 1. Если числа  и  взаимно просты, причем  и , то числа  и  также взаимно просты.

Доказательство. По теореме из взаимной простоты чисел  и  следует, что найдутся такие целые числа  и , что . Из определения делимости , , где  и   – целые числа. Тогда 

, а, значит, числа  и  взаимно просты.

Следствие 2. Рассмотрим целые числа ,  и . Если  и , то .

Доказательство. По теореме условие  можно записать в

следующем виде: , где  и  – целые числа. По определению делимости условие  означает, что найдется такое целое число , что . Умножим обе части последнего равенства на , получим . Но , тогда

             .

Поскольку – целое число, последнее равенство означает, что .