Теорема (Основная теорем о евклидовых кольцах).
Пусть К – евклидово кольцо, тогда любые элементы имеют наибольший общий делитель и, более того, 
такие, что d=НОД(a,b)=au +bv.
Доказательство.
а) Применяя свойство деления с остатком получим табличку уменьшающихся остатков. Так как степень каждого остатка – натуральное число, а натуральные числа не могут убывать бесконечно, то табличка будет конечной, а последний остаток нулевым.
В нашей табличке получилось n+2 строки. Какой же из участвующих в ней элементов является долгожданным НОД? Это последний ненулевой остаток rn. Для того, чтобы убедиться, что d=rn, нужно проверить оба свойства НОД. Прежде всего, просматривая табличку снизу вверх, убеждаемся, что rn делит a и b. В самом деле, последняя строка нам гарантирует, что rn\rn-1. Из предпоследней строки следует, что rn\rn-2 и т.д. Из третьей строки следует, что rn\r, из второй, что делит b, а из первой, что rn\a.
Теперь проверим, что rn - наибольший делитель, т.е., что он делится на любой s такой, что s\a и s\b. Теперь просматриваем нашу табличку сверху вниз. Из первой строчки следует, что s\r, из второй, что s\r1 и т.д. Из предпоследней строки следует, что s\rn. Таким образом, последняя строка даже не понадобилась.
б) Осталось выразить остаток rn через исходные элементы a и b. Для этого опять просматриваем нашу табличку снизу вверх. Из предпоследней строки получаем rn =rn-2+(-qn)rn-1, из третьей снизу rn-1=rn-3+(-qn-1)rn-2, поэтому
rn=rn-2+(-qn)rn-1=rn-2+(-qn)(rn-3+(-qn-1)rn-2)=rn-2(1+(-qn)(-qn-1))+rn-3(-qn).
Поднимаясь снизу вверх, мы последовательно выразим rn через rn-2 и rn-1, потом через rn-3 и rn-2 и т.д. И, наконец, через a и b.
□
Таким образом, в кольце целых чисел и кольце многочленов над полем всегда можно эффективно найти НОД. Алгоритм, приведенный выше, его называют алгоритмом Евклида, реализован в большинстве компьютерных систем, в том числе и в тех, что используются для нужд криптографии.
Данная теорема имеет массу приложений, например, с ее помощью строятся поля Галуа.
Дата добавления: 2015-11-28; просмотров: 1152;