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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее, разделим на , получим , при этом . Продолжим процесс деления:

, ;

, ;

, ;

, .

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

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

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

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

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

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

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

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

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

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

.

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

и .

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

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

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

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