ГЛАВА 4. АРИФМЕТИКА ПОЛЕЙ ГАЛУА

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

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

4.1. КОЛЬЦО ЦЕЛЫХ ЧИСЕЛ

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

Говорят, что целое число делится на целое число или что делит (или что является делителем если где а — некоторое целое число. Если и делит и делится на то Действительно, для некоторых целых чисел следовательно, должно равняться 1. Так как целые, то и а и должны быть либо I, либо

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

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

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

Теорема 4.1.1 (алгоритм деления). Для каждой пары целых чисел при отличном от нуля найдется единственная пара целых чисел (частное) и (остаток), таких, что где 0 с

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

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

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

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

Теорема 4.1.2.

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

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

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

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

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

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

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

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

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

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

Доказательство. Последний остаток в теореме 4.1.3 равен Воспользуемся множеством выписанных в этой теореме уравнений, чтобы исключить все остальные остатки. Это даст выражение для в виде линейной комбинации с целочисленными коэффициентами.