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

Если К – Евклидово кольцо, то

Что будет, если степень степени ? То будет (будет только остаток)

- это элемент, который делит и делится на все остальные делители

Замечание: Не во всех кольцах НОД существует (в Евклидовых существует).

Теорема: в Евклидовых кольцах существует НОД о он определен однозначно, с точностью до умножения на обратный элемент, т.е. все НОД-ы ассоциированы между собой.

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

(так как у нас есть ассоциативность)

(т.к. кольцо К без делителей 0-ля)

Построим НОД в явном виде

Пусть - последний остаток,такой обязательно существует, т.к. степень элемента а, а – конечное число

В таблице получилось строки, главные действительные лица – остатки r, а q - коэффициенты.

НОД – это последний остаток , . Нужно проверить, что он общий, т.е. . Просматриваем нашу таблицу снизу вверх.

По определению делимости из последней строки следует, что , а теперь используем 4 свойства делимости. из последней скобки получили, что делит , из третей снизу следует, что делит и т.д. из первой будет следовать, что делит само , значит - общий делитель.