Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.2. Идеалы и классы вычетов целых чисел

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

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

Если делитель делитель то либо либо потому что если делится на делится на то для некоторых целых а и число следовательно, так что произведение должно быть равно 1, Поэтому каждое из чисел а и b должно быть равно либо либо — 1.

Для любой пары целых чисел существует единственная пара целых чисел где частное и остаток, таких, что

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

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

Так как d является делителем 973 и 301, то d должно быть делителем и остатка 70. Так как d-делитель 301 и 70, оно является делителем 21. Так как делитель 70 и 21, оно является делителем и 7. С другой стороны, 7 является делителем 21, следовательно, и делителем 70, следовательно, и делителем 301 и. наконец, также и 973, и поэтому d должно быть равно 7.

Теперь полученные равенства могут быть использованы для того, чтобы представить 7 в виде (6.3), так как

Теорема 6.2. Совокупность целых чисел образует идеал тогда и только тогда, когда она состоит из всех чисел, кратных некоторому целому числу.

Доказательство. Пусть наименьшее целое положительное число в идеале и 5 — любое другое целое число, принадлежащее идеалу. Тогда наибольший общий делитель этих чисел d принадлежит идеалу, потому что, по определению идеала, оба слагаемых в правой части соотношения (6.3) принадлежат идеалу, и, следовательно, их сумма также принадлежит идеалу. Так как наименьшее положительное число в идеале, то Поскольку делится на то Следовательно, делится на т. е. на делится любое целое число, принадлежащее идеалу. Наконец, любое число, кратное принадлежит идеалу по определению идеала. Ч. т. д.

Идеал, который состоит из всех элементов, кратных одному из элементов кольца, называется главным идеалом, а кольцо, в котором каждый идеал главный, называется кольцом главных идеалов. Теорема 6,2 утверждает, таким образом, что кольцо всех целых чисел является кольцом главных идеалов.

Идеал, который состоит из всех чисел, кратных и самого обозначается Кольцо классов вычетов, образованное классами вычетов по идеалу называется кольцом целых чисел по модулю

Теорема 6.3. Каждый класс вычетов по модулю содержит либо 0, либо целое положительное число, не превосходящее Нуль является элементом идеала, а все целые положительные числа, не превосходящие принадлежат различным классам вычетов.

Доказательство. Если - любой элемент некоторого класса вычетов, то поскольку

принадлежит тому же самому классу вычетов и Если принадлежат одному и тому же классу вычетов, то разность является элементом идеала и, следовательно, кратна Если то, очевидно, эти числа не могут быть оба меньше, чем и неотрицательны. Ч. т. д.

Из теоремы 6.3 следует, что перечень включает каждый класс вычетов один и только один раз. Обычно классы вычетов обозначают Это обозначение используется в нашей книге, поскольку по контексту будет всегда легко понять, обозначают эти символы целые числа или классы вычетов.

Теорема 6.4. Кольцо классов вычетов по модулю является полем тогда а только тогда, когда простое число.

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

Теперь остается показать, что если простое число, то для каждого класса вычетов, кроме 0 (идеала), существует обратный. Каждый такой класс вычетов содержит целое число которое не превосходит и не равно 0. Поскольку 1 совпадает с обратным к ней элементом, можно предполагать, что Так как по предположению, простое число, то наибольший общий делитель должен быть равен либо либо 1. Но следовательно, 5 не может делиться на Поэтому наибольший общий делитель и 5 равен 1. В силу соотношения 6.3

откуда следует, что т. е. класс вычетов имеет класс своим обратным. Ч. т. д.

Построенные таким образом поля называются простыми полями, или полями Галуа, состоящими из элементов,

<< Предыдущий параграф Следующий параграф >>
Оглавление