Главная страница  Дискретный канал связи 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [ 26 ] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

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 - простое число. Для доказательства того, что кольцо является полем, надо показать, что каждый ненулевой элемент имеет мультипликативный обрат-




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [ 26 ] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189]

0.0174