8.1. Основные понятия теории чисел

Для исследования -кодов необходимо знать основы теории чисел. Настоящий раздел является вспомогательным и содержит краткое изложение основных понятий и результатов теории чисел, используемых в последующих разделах при рассмотрении -кодов. Более детальное изложение этих вопросов можно найти, например, в книгах Такаги [6] и Виноградова [7].

8.1.1. Делимость целых чисел

Пусть — целое положительное число. Произвольное целое число а единственным образом может быть представлено в виде

Целое число называется частным, а целое число остатком от деления а на или наименьшим неотрицательным вычетом по модулю Равенство (8.1) иногда записывают также в виде

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

кроме того,

8.1.2. Наименьшее общее кратное и наибольший общий делитель

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

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

делителей называется наибольшим общим делителем и обозначается через или

Если то числа называются взаимно простыми. Очевидно, что для взаимно простых чисел

Любое общее кратное двух целых чисел всегда делится на наименьшее общее кратное Кроме того, имеет место равенство

8.1.3. Простые числа и разложение на простые сомножители

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

Произвольное целое число единственным с точностью до" порядка образом разлагается в произведение попарно различных простых чисел (или их степеней

В разд. 9.1 и 9.2 рассматриваются, в частности, разложения такого типа для целых чисел вида

8.1.4. Функция Эйлера

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

Кроме того, легко проверить, что для любого целого

Если представить произвольное целое а в виде (8.7), то из приведенного ниже свойства мультипликативности функции Эйлера с учетом формул (8.8) и (8.9) получаем

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

Еще одно важное свойство состоит в том, что для произвольного целого числа а

Другими словами, сумма значений по всем которые делят а, равна а.

8.1.5. Сравнимость и классы вычетов

Если задано целое число называемое модулем, то, как можно видеть из формулы (8.1), для любого целого числа а определен остаток Если целые числа имеют один и тот же остаток, т. е. если то они называются сравнимыми по модулю и это записывается так:

В тех случаях, когда модуль сравнения понятен из контекста, вместо формулы (8.13) иногда пользуются также упрощенной записью а Очевидно, что . В действительности существует бесконечно много чисел, сравнимых с Множество всех чисел, сравнимых с называется классом вычетов, содержащим Легко видеть, что существует попарно непересекающихся классов вычетов в соответствии с значениями остатка Каждое целое число принадлежит одному из этих классов вычетов. Если взять по одному представителю каждого из этих классов вычетов, то получится полная система вычетов по модулю Полная система вычетов является коммутативным кольцом с операциями сложения и умножения по модулю Более того, если является простым числом, кольцо является полем. Часто в качестве полной системы вычетов используется совокупность наименьших неотрицательных остатков

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

8.1.6. Теоремы Эйлера и Ферма

Теорема Эйлера. Если

т. е. делится на

Эта теорема является обобщением следующей теоремы Ферма.

Теорема Ферма. Если простое число и а не делится на то

Умножив обе части последнего равенства на а, получим

Последнее равенство справедливо для любого а.

8.1.7. Показатели экспоненты и примитивные корни

Пусть Рассмотрим бесконечную последовательность

Согласно теореме Эйлера, существует целое положительное число такое, что Минимальное целое положительное число удовлетворяющее этому условию, называется показателем числа а по модулю Иногда называется также порядком а по модулю Показатель а по модулю обозначают следующим образом:

Если то числа являются попарно несравнимыми по модулю Далее, если то делит Очевидно, что делит Наконец, если показатель а по модулю равен и то показатель по модулю равен

Для примера в табл. 8.1 указаны вычеты (остатки) по модулю взаимно простые с (т. е. дана приведенная

Таблица 8.1 (см. скан) Приведенная система вычетов по модулю и показатели этих вычетов

система вычетов) и их показатели. В этом случае и из таблицы видно, что не существует целых чисел с показателем Это означает, что никакое число, принадлежащее приведенной системе вычетов по модулю 45, не порождает эту систему. Другими словами, не существует такого целого числа а, что является приведенной системой вычетов по модулю 45. Кроме того, не существует и целого числа, которое имело бы показатель 8 по модулю 45. Таким образом, следует заметить, что не каждый делитель числа является показателем какого-либо целого числа по модулю 45.

Если показатель а по модулю равен т.е. если то а называется примитивным элементом по модулю Как показывает приведенный выше пример, примитивные элементы существуют не для всех целых чисел. Известно, что примитивные элементы существуют только для целых чисел вида

где простое нечетное число и . Более того, для каждого из этих чисел существует примитивных элементов. Если является примитивным элементом по модулю , то является примитивным элементом также и по модулю . Кроме того, если один из примитивных элементов по модулю то все примитивные элементы по модулю представляют собой числа

Например, минимальным положительным примитивным элементом по модулю является 2. Следовательно,

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

Таблица 8.2 (см. скан)

Так как то существуют четыре примитивных корня для 13, а именно

Необходимое условие существования в приведенной системе вычетов по модулю числа о, принадлежащего показателю можно получить, используя определенную ниже Я-функцию Кармайкла. Эта функция определяется на множестве целых чисел следующим образом:

3) если где простое число, то

4) если — попарно различные нечетные простые числа, то

Из определения и теоремы Эйлера следует, что

Известно, что целое число взаимно простое с имеющее показатель (другими словами, элемент а приведен ной системы вычетов показателя ), существует тогда и только тогда, когда является делителем Например, при

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

Если , то

8.1.8. Мультипликативные группы и их разложение

Приведенная система вычетов по модулю является коммутативной группой с операцией умножения по модулю Обозначим эту группу через а именно

Если нечетное число, то в входит число 2. Если показатель 2 по модулю равен т.е. если то является делителем а следовательно, и делителем Множество степеней числа 2, вычисленных по модулю образует подгруппу порядка группы Как хорошо известно, группу можно разложить на непересекающиеся смежные классы по этой подгруппе. Число таких смежных классов будет в точности равно

Рассмотрим, например, разложение группы . В этом случае т. е. в входит 48 целых чисел. Показатель числа 2 по модулю 105 определяется из соотношений

Разложение группы на смежных класса по подгруппе порядка 12 задается табл. 8.3.

Таблица 8.3 (см. скан) Разложение по подгруппе

Предположим опять, что нечетное число. Если не является простым, то существуют вычеты по модулю не являющиеся взаимно простыми с Пусть а — один из этих вычетов. Заметим, что а не является элементом Однако если то следовательно,

Группу точно так же, как и можно разложить на смежных классов по подгруппе порядка где показатель числа 2 по модулю Эту процедуру можно выполнить для всех делителей модуля При этом исходный вычет а может быть найден путем умножения вычета, принадлежащего на делитель Таким образом, для произвольного нечетного множество вычетов по модулю полная система вычетов) разлагается на смежные классы, не имеющие общих элементов. Отсутствие общих элементов следует из формулы (8.12) и того, что при множества не имеют общих элементов. Следует также заметить, что поскольку показатели числа 2 по модулю для разных различны, то в разных смежных классах содержится неодинаковое число элементов.

Пусть, например, Рассмотрим мультипликативную группу В данном случае следовательно, состоит из 24 элементов. Группа разлагается на смежных класса, как показано в табл. 8.4.

Таблица 8.4 (см. скан) Разложение

Соответствующие вычеты а по модулю 105, такие, что представлены в табл. 8.5.

Таблица 8.5 (см. скан) Вычеты по модулю 105, соответствующие двум смежным классам группы

Аналогично, рассматривая мультипликативную группу при получаем, что Группа из четырех элементов и соответствующие вычеты по модулю 105 приведены соответственно в табл. 8.6а и 8.6б.

Таблица 8.6а (см. скан)

Таблица 8.6б (см. скан)

8.1.9. Квадратичные вычеты и символ Лежандра

Пусть такие целые числа, что Если сравнение

имеет решение в целых числах, то число а называется квадратичным вычетом по модулю . В противном случае, т. е. если (8.19) не имеет решения в целых числах, число а называется квадратичным невычетом.

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

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

Введенная величина называется символом Лежандра. Имеет место следующее сравнение:

включающее как частный случай также сравнение (8.20). Для произвольных нечетных простых чисел справедливы также следующие законы;

1) Первое дополнение к закону взаимности

2) Второе дополнение к закону взаимности

3) Закон взаимности

В заключение сформулируем еще одно необходимое и достаточное условие для произвольного модуля где нечетные простые числа. Для того чтобы число а, взаимно простое с модулем, было квадратичным вычетом, необходимо и достаточно, чтобы выполнялись следующие условия: 1) если если Кроме того, заметим, что если 2 является квадратичным вычетом по модулю то 2 будет также и квадратичным вычетом по модулю

8.1.10. Круговые многочлены и их сомножители

Как хорошо известно, алгебраическое уравнение

имеет различных корней Эти корни называются корнями степени из 1 и часто представляются в виде комплексных чисел:

Если корень обладает тем свойством, что все элементы различны, то он называется примитивным корнем степени из 1. Элемент является примитивным корнем степени из 1 тогда и только тогда, когда Следовательно, всего существует примитивных корней из 1. Если является примитивным корнем степени из 1, а кроме того, и корнем некоторого уравнения то число должно делить

Если различные корни степени из 1, то

Те из корней для которых являются примитивными корнями степени из 1. Каждый из остальных корней является корнем некоторой степени из 1, где один из делителей числа Пусть многочлен от х, корнями которого являются только примитивные корни степени из 1, а именно пусть

где — произведение по всем примитивным корням степени из 1.

Заметим, что имеет степень Поскольку каждый корень степени из 1 является примитивным корнем степени из 1 для некоторого делителя числа то

где — произведение по всем делителям числа

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

Приведем два свойства круговых чисел и примеры таких чисел:

1) Если простое число, не являющееся делителем то необходимым и достаточным условием того, что имеет в качестве простого сомножителя число является выполнение равенства Кроме того, является делителем тогда и только тогда, когда является делителем

2) Пусть простое число, являющееся делителем а именно пусть не делит Тогда необходимым и достаточным условием того, что имеет в качестве простого сомножителя число является выполнение равенства При этом делится на но не делится

Для примера рассмотрим разложение числа 218—1 на круговые числа:

Примеры круговых чисел приведены в табл. 8.7.

Таблица 8.7 (см. скан) Примеры круговых чисел

8.1.11. Минимальное представление дроби

Как известно, любую дробь можно представить в виде

Пусть В — произвольное заданное целое число, и пусть —показатель числа по модулю В. Тогда

т. е. можно подобрать такое целое число А, что

Следовательно, для любого

Это равенство показывает, что дробная часть является периодической последовательностью с периодом

Например, дробь является десятичной последовательностью с периодом 6. Это следует из того, что При этом

Заметим, что в данном примере дробные части 1/13, 10/13, 9/13, 12/13, 3/13, 4/13 получаются циклическими перестановками

В общем случае, если взять В так, что а именно чтобы число было примитивным корнем В, то представление в виде десятичной дроби числа получается путем циклических перестановок символов в представлении в виде десятичной дроби числа Это широко применяется в теории циклических AN-кодов и ниже будет использовано в частном случае