У. Питерсон - Коды, исправляющие ошибки (1267328), страница 35
Текст из файла (страница 35)
Цель этой главы— дать минимальные сведения, необходимые для понимания следующих глав. 6.1. Идеалы, классы вычетов и кольцо классов вычетов В теории групп очень важную роль играет понятие подгруппы, и 'в частности нормального делителя. В теории колец соответствующую роль играет понятие идеала. Идеалом 1 называется подмножество элементов кольца 11, обладающее следующимн двумя свойствами: 1) 1 является подгруппой аддитивной группы кольца 11 и 2) для любого элемента а из 1 и любого элемента Г из Ю произведения аг и Га принадлежат !.
(Иногда 1 называют двусторонним идеалом.) Пример. В кольце нз положительных и отрицательных целых чисел и нуля множество всех чисел, кратных некоторому целому числу, образует идеал. Поскольку идеал является подгруппой, то по нему могут быть образованы смежные классы. В этом случае смежные классы называются классами вычетов.
Идеал образует первую строку разложения с нулевым элементом слева. Далее, любой элемент кольца, не принадлежащий идеалу, может быть выбран в качестве образующсго первого класса вычетов, а остальные элементы класса строятся прибавлением образующего к каждому элементу идеала: О=а1, аз аз.
Г,=Г1+а1, Г1+а2, Г1+аз, Г2 = Гз + а1, Гз+ а2, Гз + аз» Первыми элементами в каждой строке являются, как и прежде, элементы, не нспользованные в предыдуших строках. Конечно, все свойства смежных классов верны также для классов вычетов.
В частности, поскольку групповая операция сло- жения коммутативна, идеал являетсн нормальным делителем и сложение классов вычетов может быть определено как (г)+(з)=( +з), где (г) обозначает класс вычетов, содержащий г. При таком определении классы вычетов образуют аддитивную группу — факторгруппу, рассмотренную в равд. 2.4. Можно также определить умножение классов вычетов следующим образом: (г)(з)=( ) (6.1) Это определение справедливо только в том случае, если независимо от выбора представителей а классах вычетов, которые должны быть перемножены, соотношение (6.1) определяет в качестве про- изведения один и тот же класс вычетов. Другими словами, если г и г' принадлежат одному и тому же классу вычетов и если з и з' принадлежат одному и тому же классу вычетов, то произведения гз и г'з' должны принадлежать одному и тому же классу вычетов.
Это условие будет выполняться тогда и только тогда, когда эле- мент г'з' — гз принадлежит идеалу. Но г'з' — гз = г'з' — г'з + г'з — гз = г' (з' — з) + (г — г) з. Поскольку элементы з' — з и г' — г принадлежат идеалу, то каж- дое из двух слагаемых в правой части этого равенства тоже при- надлежит идеалу и, следовательно, идеалу принадлежит также элемент г'з' — гз. Таким образом, это определение умножения классов вычетов имеет смысл. Легко проверить, что справедливы ассоциативный и дистрибу- тивный законы: (а) ((Ь) (с)) = (а) (Ьс) = (або) = (аЬ) (с) = ((а) (Ь)) (с), (а) ((Ь) + (с)) = (а) (Ь + с) = (а (Ь + с)) = (аЬ) + (ас) = = (а) (Ь) + (а) (с); аналогично можно проверить справедливость дистрибутивного за- кона для умножения справа.
Очевидно, умножение определено для любой пары классов вычетов. Следовательно, имеет место теорема 6.1. Теорема 6.1. Классы вычетов по идеалу и некотором кольце образуют кольцо. Это кольцо называется кольцом классов вычетов. ЛР'~~ар. В кольце всех целых чисел рассмотрим идеал, обра- зуемый всеми четными целыми числами. Тогда будет два класса вычетов: 0 и четов: (0) и (1). Легко видеть, что с арифметической тачки зрения кольцо классов вычетов определяет «арифметику по м~ду~ю 6.2. Идеалы и классы вычетов целых чисел Если г, з и 1 — целые числа и гз = Г, то говорят, что 1 делится на г или что г является делителем Е Целое число р) 1, которое делится только на .+.р и на ~1, называется простым. Наибольшим оби1им делителем двух целых чисел называется наибольшее положительное целое число, являющееся делителем обоих этих чисел. Говорят, что два целых числа взаимно аростьи если их наибольший общий делитель равен 1.
Если г — делитель з и з — делитель г, то либо г = з, либо г = = -з, потому что если г делится на з и з делится па г, то для некоторых целых а и Ь число г= за и з = гЬ и, следовательно, г = гаЬ, так что произведение аЬ должно быть равно 1. Поэтому а =Ь-' и каждое из чисел а и Ь должно быть равно либо +1, либо — 1. Для любой пары целых чисел з и с( существует единственная пара целых чисел д (частное) и г (остаток), таких, что з= д9+ г, где 0(г <1а' ~.
(6.2) Этот факт известен как алгоритм деления Евклида. С помощью этого алгоритма можно получить некоторые очень важные алгебраические.свойства целых чисел. В частности, можно доказать, что любое целое число можно представить однозначно в виде произведения степеней простых чисел и что наибольший общий делитель д двух целых чисел г и з всегда можно представить в виде д=аг+ Ьз, (6.3) где а и Ь вЂ” целые числа. Приводимая ниже иллюстрация того, как можно, используя алгоритм деления, найти наибольший общий делитель, разъясняет и метод доказательства соотношения (6.3).
Наибольший общий делитель д чисел 973 и 301 может быть найден следующим образом: 973 = 3 Х 301 + 70, 301 = 4 Х 70 + 21, 70 = 3 Х 21 + 7, 21 = 3 р," 7 + О. Так как число д является делителем 973 и 301, то оно должно быть делителем и остатка 70. Поскольку число д — делитель 301 и 70, оно является делителем 21. Так как д — делитель 70 и 21, оно является делителем и 7. С другой стороны, 7 является делителем 21, следовательно, и делителем 70, следовательно, и делителем 301 и, наконец, также и делителем 973, и поэтому д должно быть равно 7.
Теперь полученные равенства могут быть использованы для' того, чтобы представить 7 в виде (6.3), так как 7 = 70 — 3 Х 21 = = 70 — 3 Х (301 — 4 Х 70) = = — 3 Х 30! + 13 Х 70 = = — 3 Х 301 + 13 Х (973 — 3 Х 30!) = = 13 Х 973 — 42 Х 301. Теорема 6.2. Совокупность целых чисел образует идеал тогда и только тогда, когда она состоит из всех чисел, кратных некоторому целому числу. Доказательство. Пусть г — наименьшее целое положителыюе число в идеале и з — любое другое целое число, принадлежащее идеалу.
Тогда наибольший общий делитель этих чисел с1 принадлежит идеалу, потому что по определению идеала оба слагаемых в правой части соотношения (6.3) принадлежат идеалу и, следоватсльпо, их сумма также принадлежит идеалу. Так как г — наименьшее положительное число в идеале, то г( д.
Поскольку г делится на д, то д ~ г. Следовательно, г = д и з делится на г, т. е. яа г делится любое целое число, принадлежащее идеалу. Наконец, любое число, кратное г, принадлежит идеалу по определению идеала. Ч. т. д. Идеал, который состоит из всех элементов, кратных одному из элементов кольца, называется главным идеи.1ом, а кольцо, в котором каждый идеал главный, называется кольцом главных идеалов. Согласно теореме 6.2, кольцо всех целых чисел является кольцом главных идеалов.
Идеал, который состоит из всех чисел, кратных положительному целому числу т, обозначается через (т). Кольцо классов вычетов, образованное классами вычетов по идеалу (т), называется кольцом целых чисел по модулю т. Теорема 6.3. Каждый класс вычетов по модулю т содержит либо О, либо целое положительное число, меньшее т. Нуль является элементом идеала, а все остальные целые полозсительные. числа, меньшие т, принадлежат различным классам вычетов. Доказательство. Если з — любой элемент некоторого класса вычетов, то, поскольку з =ту+ г, г — принадлежит тому же самому классу вычетов и 0 (г ( т. Если г и з принадлежат одному и тому же классу вычетов, то разность г — з является элементом идеала и, следовательно, кратна т.
Если г ~ з, то, очевидно, эти числа не могут быть оба меньше чем т и неотрицательны. Ч. т. д. Из теоремы 6.3. следует, что перечень (0), (1), (2),, (т — 1) включает каждый класс вычетов один и только один раз. Обычно классы вычетов обозначают через О, 1, 2, ..., т — 1. Это обозначение используется в данной книге, поскольку по контексту всегда легко понять, обозначают ли эти символы целые числа или же классы вычетов.
Теорема 6.4. Кольцо классов вычеюв по модулю т является полем тогда и только тогда, когда т — простое число. Доказательство. Если т — не простое число, то т = гз для некоторых целых чисел г и з, которые не кратны т. Поэтому (г)(з) = (т) = О, и если класс вычетов и обладает обратным (г)-', то и — Чг)(з) = з = К вЂ” '0 = О, что противоречит предположению. Поэтому класс вычетов (г) не может иметь обратного, и кольцо классов вычетов не является полем.
Теперь остается показать, что если т — простое число, то для каждого класса вычетов, кроме 0 (идеала), существует обратный. Каждый такой класс вычетов содержит целое число з, которое меньше чем т и не равно О. Поскольку 1 совпадаст с обратным к ней элементом, можно предполагать, что з ) !. Так как т по предположению — простое число, то наибольший общий делитель з и т должен быть равен либо пг, либо 1. Но т ) з, и, следовательно, з не может делиться на т. Поэтому наибольшии общий делитель т и з равен 1.
В силу соотношения (6.3) 1 =ап1+ Ьз, и отсюда следует, что (Ь)(з) = (1), т. е. класс вычетов (Ь), яв- ляется обратным к классу вычетов (з). Ч, т. д. Построенные таким образом поля называются простыми полями или полями Галуа из р элементов Бг (р). 6.3. Идеалы многочленов и классы вычетов Рассмотрим теперь многочлены 1(Х) от одною неизвестного (нли переменного) Х с коэффициентами из некоторого поля г: ((Х)=(ь+(1Х+ )гХг+ - ° +) Х".
Степенью многочлена называется наибольшая степень Х в слагаемом с ненулевым коэффициентом. Степень нулевого много- члена равна О. Многочлен называется нормированным, если коэффициент при наивысшей степени Х равен 1. Многочлены можно складывать и умножать обычным путем; они образуют кольцо. Если г(Х), з(Х) и 1(Х) — многочлены и г(Х)з(Х)=1(Х), то говорят, что многочлен 1(Х) делится на многочлен г(Х) или что многочлен г(Х) является делителем многочлена 1(Х) или что мно- гочлеп г(Х) является множителем для ((Х).
Многочлен р(Х) степени и, который не делится ни на какой многочлен степени, меньшей чем и, но большей чем О, называется неприеодимым. «таибольшим оби(им делителем двух многочленов называется нормированный многочлеи наибольшей степени, который является делителем для обоих многочленов. Говорят, что два многочлена взаимно просты, если их наибольший общий делитель равен Е Степень произведения двух многочленов равна сумме их степеней, Ненулевой многочлен степени О является элементом поля и поэтому имеет обратный элемент, но многочленов более высоких степеней, которые обладали бы обратными элементами, не существует.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
