Алгоритм Евклида

Дана пара целых чисел (m,n). Считаем n остатком с номером 1. Первый шаг алгоритма Евклида – делим m на n с остатком, а далее делим остаток на вновь получившийся остаток покуда этот вновь получившийся остаток не станет равным 0. Этот момент обязательно наступит, так как модули остатков строго убывают. Более точно: обозначим и образуем последовательность делений с остатком:

Для чего предназначен этот алгоритм? Например, для вычисления наибольшего общего делителя пары чисел m и n. Обозначим через НОД(m,n) – наибольшее натуральное число, делящее как m так и и n. Дополнительно, по определению полагаем НОД(0,0)=0.

Если то , т.е. согласно первой строке алгоритма. Но тогда d делит и и т.д. вплоть до . Эту цепочку импликаций можно обратить: если , то d делит , а затем делит и т.д. вплоть до n и m. Доказано, что

-- последний ненулевой остаток в алгоритме Евклида. Попробуем на практике, взяв m=900 и n=1155

Итог: НОД(900,1155)=15. Мы могли бы уменьшить числа, пользуясь правилом

Тогда НОД(900,1155)=5⋅ НОД(180,231)=15⋅ НОД(60,77). Но далее, применяя алгоритм Евклида, мы записали бы опять шесть строк и пришли к выводу, что НОД(60,77)=1. Числа m и n, наибольший общий делитель которых равен 1, называются взаимно простыми (обозначение m⊥ n). Оказывается число d=НОД(m,n) можно записать в виде линейной комбинации своих аргументов:

Это важное соотношение позволяет доказать известное правило для простых чисел p:

из которого в свою очередь вытекает единственность разложения на простые множители. Однако, все по порядку: докажем сначала (2). Проходим еще раз по строкам алгоритма Евклида сверху в низ: -- выражается в виде линейной комбинации, тогда и

также выражается через m и n в виде линейной комбинации. Дойдя до последней строки, видим, что и выражается через m и n в виде линейной комбинации. Заметим, что если выполняется соотношение (2), то |d | заведомо есть НОД чисел m и n. Для чисел получаем:

Докажем теперь правило (3). Пусть , т.е. для некоторого k. Если , то все доказано. Иначе p⊥ k, ибо p простой элемент. Пользуясь (1), найдем элементы s,t такие, что 1=ps+at. Тогда

откуда .

Предположим теперь, что

-- два разложения в произведение простых элементов: простые и -- попарно различны. Доказательство ведем индукцией по числу . База индукции – случай s=t=1, очевиден. Так как делит произведение , то делит один из сомножителей . Но этот сомножитель также есть простой элемент и поэтому .

Сокращая левую и правую часть соотношения (4) на , получаем аналогичное равенство, но с меньшим числом сомножителей. Продолжая этот процесс, дойдем до равенства и, в частности, до равенства s=t. Этим и завершается доказательство основной теоремы арифметики.

Придадим матричную трактовку алгоритму Евклида (о матрицах см. следующий параграф). Перепишем последовательность делений с остатком в матричном виде:

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

Заметим, что слева стоят матрицы с определителем -1, поэтому их произведение, обозначим его , имеет определитель и, значит, оно обратимо в кольце целочисленных 2х2-матриц. Доказана

ТЕОРЕМА. Для любой пары целых чисел с найдется обратимая 2х2-матрица над ℤ такая, что

.

В частности, найдутся числа такие, что .

В нашем численном примере

Вторую строку матрицы Q можно найти с помощью НОК(m,n) – наименьшего общего кратного чисел m и n, т.е. наименьшего натурального числа, кратного как m так и n. Оно связано с НОД соотношением

и в нашем числовом примере равно НОК(900,1155)=900⋅ 1155/15=69300. Тогда 69300=900⋅77=1155⋅ 60 и поэтому -77⋅ 900+60⋅ 1155=0. Вот отсюда и берется вторая строка (-77, 60). Почему определитель матрицы Q, полученной таким образом, будет заведомо ± 1 (мы его сделали +1, за счет корректировки знаков второй строки)? Ответ в упр. ___

Построим алгоритм, позволяющий вычислить матрицу Q (см. файл Алгоритм Евклида.xlsm). Основная идея алгоритма заключается в том, что по мере продвижения по строкам алгоритма Евклида, мы сначала от единичной матрицы переходим к матрице , затем к матрице и т.д., пока не дойдем до итоговой матрицы .

Sub Matrix2() Dim m As Integer Dim n As Integer Dim a As Integer Dim b As Integer Dim s As Integer Dim r As Integer

Dim Q(1 To 2, 1 To 2) As Integer ‘ Задание целочисленной 2×2-матрицы m = Cells(4, 2): n = Cells(5, 2)

For i = 1 To 2 ' В начале Q инициализируем единичной матрицей For j = 1 To 2 If i = j Then Q(i, j) = 1 Else Q(i, j) = 0 Next Next

Do Until n = 0 s = m \ n: r = m - n * s a = Q(1, 1): b = Q(1, 2): Q(1, 1) = Q(2, 1): Q(1, 2) = Q(2, 2) Q(2, 1) = a - s * Q(2, 1): Q(2, 2) = b - s * Q(2, 2) m = n: n = r Loop Cells(7, 3) = m: Cells(8, 3) = Abs(Q(2, 1) * Cells(4, 2)) Cells(12, 1) = Q(1, 1): Cells(12, 2) = Q(1, 2) Cells(13, 1) = Q(2, 1): Cells(13, 2) = Q(2, 2) Cells(12, 4) = "НОД": Cells(12, 5) = m

End Sub