4.1. кольцо целых чисел 86

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

В общем случае в кольце целых чисел деление возможно не всегда, зато имеют место две почти столь же важные операции, а именно сокращение и деление с остатком. В силу возможности сокращения кольцо целых чисел является областью целостности. Возможность деления с остатком (известного как алгоритм деления) обычно доказывается с помощью конструктивной процедуры. Мы сформулируем его в виде самоочевидной теоремы.

Теорема 4.1.1 (алгоритм деления). Для каждой пары целых чисел cud при отличном от нуля d найдется единственная пара ц-лых чисел Q (частное) и s (остаток), таких, что с = dQ -\- s, где О < S < I d .

Обычно нас будет больше интересовать не частное, а остаток. Мы будем часто записывать остаток в виде равенства

S = Rd [с],

которое читается так: «s является остатком от деления с на d». Другим обозначением является

S = с (mod d).

Соотношение такого вида называется сравнением и читается так: «s сравнимо с с по модулю d». Оно означает, что при делении на d числа S и с имеют один и тот же остаток, но s не обязательно меньше d.

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

Теорема 4.1.2.

(i) Ra [а +b] = Ra \Ra [a] + Ra Щ].

(ii) Rd [a-b] = Ra \Ra \a]-Ra [b\\.

Доказательство предоставляется читателю в качестве упражнения. □

Используя алгоритм деления, можно найти наибольший общий делитель двух целых чисел. Например, НОД (814, 187) находится следующим образом:

814 = 4X187 +66, 187 = 2x66 f 55, 66 = 1X55 + 11, 55 = 5X11 +0.

86 гл. 4. Арифметика полей галуа

Так как НОД (814, 187) делит и 814, и 187, то он должен делить и остаток 66. Так как он делит и 187, и 66, то он делит и 55. Так как он делит и 66, и 55, то он делит и 11. С другой стороны, 11 делит 55, а поэтому и 66, и 187, и, наконец, также 814. Следовательно, НОД (814, 187) равен 11.

Теперь можно выразить 11 в виде линейной комбинации чисел 814 и 187, начиная снизу выписанной выше последовательности и поступая следующим образом:

11 = 66 - 1 X 55 =

= 66 - 1 X (187 - 2 X 66) = 3 X 66 ~ 1 X 187 =

= 3 X (811 - 4 X 187) 1 X 187 = 3 X 814 - 13 X 187.

Следовательно, мы выразили НОД (814, 187) в виде линейной комбинации чисел 814 и 187 с коэффициентами из кольца целых чисел, а именно

НОД (814, 187) = 3 X 814 - 13 X 187.

Эти рассуждения могут быть проведены в общем виде для произвольных целых чисел / и s и позволяют доказать приведенные ниже теорему и следствие.

Теорема 4.1.3 (алгоритм Евклида). Наибольший общий делитель двух различных ненулевых целых чисел г и s может быть вычислен итеративным применением алгоритма деления. Предположим, что г <s и оба эти числа положительны; тогда алгоритм состоит в следующем:

S = Qr + /"i, г = Qai + -2,

f n-1 - Qn+ln>

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

Наконец, мы приходим к важному и интуитивно не очевидному результату теории чисел.

Следствие 4.1.4. Для любых целых чисел г и s существуют целые числа а и Ь, такие, что

НОД (/-, S) = аг + bs.

Доказательство. Последний остаток в теореме 4.1.3 равен НОД (/", s). Воспользуемся множеством выписанных в этой теореме уравнений, чтобы исключить все остальные остатки. Это даст выражение для /„ в виде линейной комбинации / и s с целочисленными коэффициентами. □

4.2. КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ

Имеется очень важная конструкция, позволяющая по заданному кольцу построить новое кольцо, называемое кольцом отношений. В случае произвольного кольца для построения кольца отношений строятся смежные классы, однако в случае кольца целых чисел кольцо отношений строится просто. В некоторых случаях это построение приводит к полям (в случае, когда кольцо является областью целостности).

Определение 4.2.1. Пусть д - положительное целое число. Кольцом отношений, именуемым также кольцом целых чисел по модулю q и обозначаемым через Z /(q), называется множество {О, 1, q- 1} с операциями сложения и умножения, определяемыми равенствами а b ~ Rg [а + fe], a-b = Rq [аЬ].

Элементы, обозначенные через О, 1, ? - 1, принадлежат как Z, так и Z/{q). Пожалуй, лучше под элементами из Z/{q) понимать не первые q элементов из Z, а некоторые другие объекты, обозначенные таким же образом. Произвольный элемент а из Z можно отобразить в Z/(q), полагая а = Rg 1а]. Два элемента а и b из Z, отображаемые в один элемент из Z/(<7), сравнимы по модулю q VI а = b -\- mq для некоторого целого т.

Теорема 4.2.2. Кольцо отношений Z l(cj) является кольцом.

Доказательство предоставляется читателю в качестве упражнения. □

Как показывают примеры из § 2.4, арифметику полей GF (2) и GF (3) можно описать как сложение и умножение по модулю 2 и 3 соответственно, а арифметику в поле GF (4) так описать нельзя. Таким образом, в принятой нами символике GF (2) = = Z/(2), GF (3) = Z/(3), GF {i)фZ/ii). Общий результат дается следующей теоремой.

Теорема 4.2.3. Кольцо отноилений Zl{q) является полем тогда и только тогда, когда q равно простому числу.

Доказательство. Предположим, что q - простое число. Для доказательства того, что кольцо является полем, надо показать, что каждый ненулевой элемент имеет мультипликативный обрат-