8.8. НАИБОЛЬШИЕ ОБЩИЕ ДЕЛИТЕЛИ И АЛГОРИТМ ЕВКЛИДА

Определение. Пусть положительные целые числа. Положительное целое число называется наибольшим общим делителем чисел (его часто обозначают через , если

1) g делит

2) всякий общий делитель чисел делит

Легко показать, что для положительных целых чисел такое число единственно. Например,

Алгоритм Евклида для вычисления состоит в вычислении последовательности остатков где ненулевой остаток от деления на нацело делит (т. е. ). В этой ситуации

Пример 8.8. В примере, приведенном выше, Поэтому и НОД

Теорема 8.15. Алгоритм Евклида правильно находит значение

Доказательство. Этот алгоритм вычисляет , то алгоритм, очевидно, заканчивает работу. Кроме того, любой общий делитель чисел делит и любой общий делитель чисел делит Следовательно, Очевидно, так что теорема доказана.

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

Алгоритм 8.6. Расширенный алгоритм Евклида

Вход. Положительные целые числа

Выход. и такие целые числа х и у, что

Метод. Применяем программу, приведенную на рис. 8.6.

Рис. 8.6. Расширенный алгоритм Евклида.

Пример 8.9. Если то для чисел получаем значения

Заметим, что

Ясно, что алгоритм 8.6 правильно вычисляет поскольку очевидно, что числа образуют требуемую последовательность остатков. В следующей лемме описывается важное свойство чисел вычисляемых алгоритмом 8.6.

Лемма 8.4. В алгоритме 8.6

Доказательство. Равенство (8.23) справедливо для в силу строки 1 алгоритма 8.6. Допустим, что (8.23) справедливо для Тогда в силу строки в силу строки 6. Следовательно,

По предположению индукции и в силу (8.24)

Так как в силу строки 4, то лемма доказана.

Заметим, что лемма 8.4 даже не зависит от способа вычисления в строке 3, хотя строка 3 существенна, чтобы гарантировать, что алгоритм 8.6 действительно вычисляет Суммируем эти замечания в следующей теореме.

Теорема 8.16. Алгоритм 8.6 вычисляет и такие числа х и у, что

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

Введем некоторые обозначения, которые понадобятся нам в следующем разделе.

Определение. Пусть целые числа и соответствующая последовательность остатков. Определим -матрицу если ясно, каковы для условиями

Пример 8.10. Пусть последовательность остатков есть 57, 33, 24, 9, 6, 3, а частные равны 1, 1, 2, 1. Тогда

Два интересных свойства этих матриц описаны в следующей лемме.

Лемма 8.5.

где числа определяются расширенным алгоритмом Евклида.

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

Заметим, что все построения этого раздела годятся и для полиномов от одной переменной. Надо лишь учесть, что, в то время как наибольший общий делитель двух целых чисел определяется однозначно, для полиномов с коэффициентами из некоторого поля наибольший общий делитель единствен только с точностью до умножения на элемент поля. Иными словами, если делит полиномы и всякий другой их делитель тоже делит то полином где с — отличная от нуля постоянная, также обладает этим свойством. Нас удовлетворит любой полином, который делит и делится на любой их делитель. Чтобы обеспечить единственность, мы могли бы (но не будем) требовать, чтобы наибольший общий делитель был нормированным, т. е. чтобы коэффициент при его старшем члене был равен 1.