Лекции по дискретной математике, страница 3

Сокращение представляет собой слабую форму деления и озна­чает, что если аb = ас, то b = с.

Теорема 1.3.3. Если в произвольном поле аb = ас и а ≠ О, то b = с.

Доказательство. Умножить на а^-1.

Некоторые кольца могут также удовлетворять этому условию сокращения, но все-таки не быть полями. Простым примером служит кольцо целых чисел. В этом кольце сокращение возможно, но приведенное для теоремы 1.3.3 доказательство не проходит, так как в этом кольце не существует элемента а^-1. Кольца, в ко­торых всегда возможно сокращение, имеют специальное название.

Определение 1.3.4. Коммутативное кольцо, в котором b = с, если аb = ас и элемент а отличен от нуля, называется областью целостности.

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

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

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

|

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

Говорят, что целое число s делится на целое число r или что r делит s (или что r является делителем s),если rа=s, где а-не­которое целое число. Если r и делит s,и делится на s, то r=±s. Действительно, r=sа и s=rb для некоторых целых чисел а и b;следовательно, г=rаb и аb должно равняться 1.Так как а и b-целые, то и a, и b должны быть либо 1, либо - 1.

Положительное целое число р > 1, которое делится только на ±р или ±1, называется простым. Положительное целое число, большее 1, не являющееся простым, называется составным. Наибольший общий делитель двух целых чисел г и s обозначается через НОД (r, s) и определяется как наибольшее положительное число, которое делит оба из них. Наименьшее общее кратное двух целых чисел r и s обозначается через НОК (r, s) и определяется как наименьшее положительное число, которое делится на оба из них. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1.

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

Теорема 2.1.1 (алгоритм деления). Для каждой пары целых
чисел с и d при отличном от нуля d найдется единственная пара
целых чисел Q, (частное) и s (остаток), таких, что с=dQ+s,
где 0≤ s < | d\.

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

s ≡ R_d [с],

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

s = с (mod d).

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

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

Теорема 2.1.2.

1. R_d(a+b)=R_d{ R_d (a) + R_d (b) }

2 . R_d(a*b)=R_d{ R_d (a) *R_d (b) }

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

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

814 = 4x187 +66,

187 = 2x66+55,

66 = 1x55 + 11,

55 = 5x11 +0.

Так как НОД (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 – 1x (187- 2x 66) =

= 3 x 66 — 1 x 187 = 3 x 814 — 13 x 187.

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

НОД (814, 187) = 3 x 814 — 13 x 187. '.

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

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

s = Q₁.r + r_1,

r = Q₂.r₁+ r₂,

r_\ = Q₃.r₂ + r₃,

r_n-1=Q_n+1r_n.

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

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

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

НОД (r, s} = аr + bs.

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

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

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

Определение 2.2.1. Пусть q — положительное целое число. Кольцом отношений, именуемым также кольцом целых чисел по модулю q и обозначаемым через Z /(q), называется множество {0, 1, 2, … , q-1} с операциями сложения и умножения, опреде­ляемыми равенствами а + b = R._q (а + b), а·b = R_q (аb).

Элементы, обозначенные через 0, 1, … ,q-1, принадлежат как Z, так и Z/(q). Пожалуй, лучше под элементами из Z,/(q) по­нимать не первые q элементов из Z, а некоторые другие объекты, обозначенные таким же образом. Произвольный элемент а из Z можно отобразить в Z/(q), полагая а = R_q. [а]. Два элемента а и b из Z, отображаемые в один элемент изZ\(q), сравнимы по модулю q и а = b + mq для некоторого целого т..

Теорема 2.2.2. Кольцо отношений Z\ (q) является кольцом.

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

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

Теорема 2.2.3. Кольцо отношений Z/(q) является полем тогда и только тогда, когда q равно простому числу.

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

ный. Пусть s — ненулевой элемент кольца; тогда 1 ≤ s ≤ q-1. Так как q просто, то НОД (.s, q) = 1, и в силу следствия 1.1.4

1 = аq+bs

для некоторых а и b. Таким образом, -^;
1 =R_q(1)= R_q(аq+bs)= R_q{R_q(аq) + R_q(bs)}= R_q(bs)= R_q{R_q(b) R_q(s)}=

=R_q{R_q(b) ,s}

Следовательно, элемент R_q(b) является мультипликативным обратным элементуsотносительно операции умножения по модулю q.Теперь допустим, что q — составное число. Тогда q=rs.. Если данное кольцо представляет собой поле, то r имеет обратный r^-1 , и поэтому s= R_q(s)= R_q(r^-1rs)= R_q(r^-1q)=0

Но s≠О, так что мы получили противоречие. Следовательно, рассматриваемое кольцо не является полем.

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

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Китайская теорема об остатках будет доказана в два этапа. Сначала мы докажем един­ственность решения, а затем его существование.

Теорема .2.2.4. Для заданного множества из k целых положи­тельных попарно взаимно простых чисел m₁, m₂, ..., m_к и множе­ства неотрицательных целых чисел с₁ с₂, ..., с_к при с_i < m_i система сравнений

c_i = с (mod т_i;), i=1,2, ,k ,

имеет

не более одного решения с в интервале 0≤ c > П^k_i-1 m_i

Доказательство. Предположим, что сиc' являются двумя лежащими в рассматриваемом интервале решениями. Тогда с =Q_i m_i +c_i и c'=Q_i'm_i+c_i и, следовательно, с — с' кратно m_i для каждого i, а так как m_i по­парно взаимно просты, то с — с кратно П^k_i-1 m_{i .}. Но число с — с' лежит между — (П^k_i-1 m_i — 1) и П^k_i-1 m_i— 1. Единственным по­ложительным числом, удовлетворяющим этим условиям, является с — с' =0. Следовательно, с = с' .

Для того чтобы практически найти решение выписанной в тео­реме 2.3.1 системы сравнений, воспользуемся следствием 2.1.4 из алгоритма Евклида, согласно которому в кольце целых чисел

НОД (г, s) =аг + bs для некоторых целых а и b.

Для заданного множества попарно взаимно простых положи­тельных целых чисел m₁, m₂, ..., m_к, положим М = П^k_i-1 m_i и М_i = М/ m_i. Тогда НОД (М_i,_ь т,) = 1, и, следовательно, суще­ствуют такие целые N_i, и n_i, что N_i M_i +n_im_i=1.