Основные алгебраические структуры (стр. 30 )

Определение. Сконструированный и описанный выше алгоритм построения евклидовых делений (1), оканчивающийся получением первого нулевого остатка r, называется алгоритмом Евклида для элементов a и b евклидова кольца R.

Покажем, что последний ненулевой остаток r алгоритма Евклида есть НОД элементов a и b:

r = (a, b) (4)

Для этого нужно протестировать r определением НОД (см. §7 Главы II: определение НОД и правую часть (1)). Действительно, равенство (1) указывает на то, что r| r. С учетом этого обстоятельства равенство (1) продуцирует делимость r| r. И т. д., «поднимаясь вверх» по равенствам (1), мы из равенств (1) и (1) «извлечем» делимости r|b и r|a, т. е., rD. Итак, остаток r подчиняется первому требованиию определения НОД. Далее, возьмем любой общий делитель δ элементов a и b: δ D. Начинаем извлекать из равенств (1) необходимые нам следствия, «спускаясь вниз» по эти равенствам: первое из них дает делимость δ|r, второе (с учетом δ|r) - делимость δ|r, и т. д., наконец, k-е даст желаемую делимость δ|r. Остаток r подчиняется, следовательно, и второму требованию определения НОД, окуда следует (4).

Вывод. Заявленная нами в начале параграфа цель достигнута: ресурсами евклидова кольца мы построили еще одну - третью - процедуру нахождения НОД двух элементов, это - алгоритм Евклида. Суть алгоритма проста: строится последовательность евклидовых делений (1), Последний ненулевой остаток r и есть искомый НОД.

Алгоритм Евклида построения НОД двух элементов евклидова кольца позволяет построить и его - НОД - линейное представление (помним, что евклидово кольцо, это и кольцо главных идеалов, в котором линейное представление НОД двух элементов существует). Действительно, пусть построен, выписан алгоритм Евклида (1). Используем уже опробованный принцип «подниматься вверх» по равенствам (1). Из равенства (1) находим r:

r = (-q)r + r (5)

Обратим внимание на формат равенства (5): это - «линейный» характер выражения r через r и r. Важна именно «линейность». Заменим теперь в полученном равенстве(5) остаток r из равенства (1) алгоритма Евклида (при необходимости иметь уверенность в рассуждениях - выписать это равенство явно). Получим - по типу (5) - «линейное» представление r - теперь уже через r и r:

r = (. . . ) r + (. . . ) r (5)

Скобками обозначены коэффициенты представления r через r и r, состав которых, как уже сказано, сейчас для нас вторичен. Продолжив «подъем вверх» по равенствам (1), мы, заменив в (5) остаток r из (1), выразим линейно r через r и r и т. д. По использовании в описанном выше режиме «подъема вверх» равенств (1) и (1), мы получим - с учетом (4) - искомое линейное представление НОД элементов a и b:

d = (a, b) = r = ua + vb (5)

Коэффициенты u и v линейного представления (5) НОД элементов a и b эффективно, конкретно высчитываются при движении от (5) к (5).

Литература (основная)

1. Курош высшей алгебры. 18 изд. Стереотип. – СПб.: Издательство «Лань», 2011 (2004,1968, 1971, 1975).рекомендовано

2. Винберг алгебры.- М.: Издательство «Факториал Пресс», 2002. – 544 с.

Литература (дополнительная)

1. Куликов и теория чисел. Учебное пособие для студентов физ.-мат. специальностей, пед. Институтов.- М.; Просвещение, 1993.

2. Алгебраические структуры с одной и двумя бинарными операциями/ , , . –Н. Новгород: НГПУ, 2005. – 98 с.

гриф УМО

3.Методические указания по изучению темы «Теория групп и колец»./сост. и др. – Н. Новгород, 1990.