Кольцо целых чисел Гаусса

дипломная работа

1.3 НОД. АЛГОРИТМ ЕВКЛИДА.

Мы пользуемся обычным для колец определением наибольшего общего делителя. НОДом двух гауссовых чисел называется такой их общий делитель, который делится на любой другой их общий делитель.

Как и во множестве целых чисел, во множестве гауссовых чисел для нахождения НОД пользуются алгоритмом Евклида.

Пусть и данные гауссовы числа, причем . Разделим с остатком на . Если остаток будет отличен от 0, то разделим на этот остаток, и будем продолжать последовательное деление остатков до тех пор, пока оно будет возможно. Получим цепочку равенств:

, где

, где

, где

……………………….

, где

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

Теорема 2. О существовании НОД.

В алгоритме Евклида, примененному к числам Гаусса и последний ненулевой остаток есть НОД().

Доказательство.

Докажем, что в алгоритме Евклида действительно получаем НОД.

1.Рассмотрим равенства снизу вверх.

Из последнего равенства видно, что .Следовательно, как сумма чисел делящихся на . Так как и , то следующая строчка даст . И так далее. Таким образом, видно, что и . То есть это общий делитель чисел и .

Покажем, что это наибольший общий делитель, то есть делится на любой другой их общий делитель.

2. Рассмотрим равенства сверху вниз.

Пусть -- произвольный общий делитель чисел и . Тогда , как разность чисел делящихся на , действительно из первого равенства . Из второго равенства получим, что . Таким образом, представляя в каждом равенстве остаток как разность чисел делящихся на , мы из предпоследнего равенства получим, что делится на .

Ч.Т.Д.

Лемма 3. О представлении НОД.

Если НОД(, )=, то существуют такие целые гауссовы числа и , что .

Доказательство.

Рассмотрим снизу вверх цепочку равенств, полученную в алгоритме Евклида. Последовательно подставляя вместо остатков их выражения через предыдущие остатки, мы выразим через и .

Ч.Т.Д.

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

Утверждение 4.

При умножении простого гауссова числа на обратимое снова получается простое гауссово число.

Утверждение 5.

Если у гауссова числа взять необратимый делитель с наименьшей нормой, то он будет простым гауссовым.

Доказательство.

Пусть такой делитель является составным числом. Тогда , где и необратимые гауссовы числа. Перейдем к нормам, и согласно (3) получим, что . Так как эти нормы натуральны, то имеем, что , а в силу (12), является необратимым делителем данного числа Гаусса, что противоречит выбору .

Ч.Т.Д.

Утверждение 6.

Если не делится на простое гауссово число , то НОД(,)=1.

Доказательство.

Действительно, простое число делится только на числа союзные с 1 или с. А так как не делится на , то на союзные с тоже не делится. Значит, их общими делителями будут только обратимые числа.

Ч.Т.Д.

Лемма 7. Лемма Евклида.

Если произведение гауссовых чисел делится на простое гауссово число , то хотя бы один из множителей делится на .

Доказательство.

Для доказательства достаточно рассмотреть случай, когда произведение содержит только два множителя. То есть покажем, что если делится на , то либо делится на , либо делится на .

Пусть не делится на, тогда НОД(,)=1. Следовательно, существуют такие гауссовы числа и , что . Умножим обе части равенства на , получим, что , отсюда следует, что , как сумма чисел делящихся на .

Ч.Т.Д.

Делись добром ;)