6.5. Определение степеней неприводимых делителей круговых многочленов

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

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

6.51. Теорема. Если где различные простые числа, то порядок по модулю равен наименьшему общему кратному порядков по модулям

Пример Предположим, что Так как порядок 2 по модулю 5 равен 4, а порядок 2 по модулю 9 равен 6, то порядок 2 по модулю 45 равен 12.

Доказательство теоремы 6.51. Имеем тогда и только тогда, когда для всех тогда и только тогда, когда кратно порядку по модулю Следовательно, тогда и только тогда, когда кратно каждому из порядков по модулям Порядок по модулю равен наименьшему из таких кратных.

6.52. Теорема. Пусть простое число, а порядок по модулю Пусть делится на и не делится на (Это определяет число Тогда для каждого либо либо и

Пример. Предположим, что необходимо найти порядок 7 по модулю Выберем Ясно, что так как делится на 24 и не делится на 25. Следовательно, согласно теореме,

Замечание. Если или то порядок 2 по модулю равен порядку 2 по модулю для остальных простых чисел порядок 2 по модулю равен умноженному на порядок 2 по модулю

Доказательство теоремы 6.52. Имеем так что Следовательно, Перемножая эти сравнения, получаем, что Следовательно, делит Так как должно быть кратно простое, то имеются только две возможности: либо либо

Если делится на но не делится на то для Для число не делится на следовательно, Это получается с помощью

индукции по из того факта, что число сравнимо с по модулю следовательно, не делится на

Последние две теоремы существенно уменьшают объем вычислений для определения порядка по модулю сводя эти вычисления к определению порядков по модулям каждого из простых делителей числа Таким образом, на самом деле нам надо рассмотреть только порядки числа для простых Наиболее очевидный результат в этом направлении дает теорема 6.53.

6.53. Теорема. При простом порядок по модулю является делителем числа

Доказательство. Согласно теореме Ферма (4.25), при любом и любом простом Если взаимно просты (а мы все время это предполагаем), то так что кратно порядку по модулю

Часто встречается задача вычисления для различных делителей d числа Наибольшее число вычислений приходится выполнять для наибольшего нетривиального делителя (или степеней 2) эти вычисления можно упростить с помощью теоремы 6.54.

6.54. Теорема. Если простое число, то если же такое простое число, что то

Доказательство. Пусть обозначает наибольшее целое число, не превосходящее х. Тогда

Для каждого к, такого, что выполняется сравнение — так что

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

Если то показатель степени для —1 является нечетным; если то показатель — четное число. в

В качестве примера использования этой теоремы определим степени неприводимых двоичных делителей многочлена Прежде всего выпишем разложение Степень этого многочлена, следовательно, равна Число 7 простое и поэтому порядок числа 2 по модулю 7 делит Ясно, что порядок 2 по модулю 7 равен 3. Каждый из остальных простых делителей 5, 11, 13 блоковой длины сравним с Из теоремы 6.54 следует, что порядок каждого из этих чисел — делитель числа но не делитель числа Порядок 2 по модулю 5 равен 4; порядок

2 по модулю 11 равен 10, порядок 2 по модулю 13 является делителем 12 и не является делителем 6 Допустимы только числа 4 и 12, и так как то порядок 2 по модулю 13 равен 12. Необходимо также определить порядок 2 по модулю 52, который равен либо 4, либо 4 5. Ясно, что правильным является второе число. Таким образом, порядок 2 по модулю 52 равен 20; порядок 2 по модулю 7 равен 3, порядок 2 по модулю И равен 10 и порядок 2 по модулю 13 равен 12. Порядок 2 по модулю равен наименьшему общему кратному чисел числу 60. Следовательно, мноючлен произведение 240 неприводимых множителей, степень каждого из которых равна 60.

Используя более тонкие методы теории круговых многочленов, можно доказать другие результаты, аналогичные теореме 6.54.

Сформулируем некоторые из них в теоремах 6.55 и 6.56.

6.55. Теорема. Если простое и , то тогда и только тогда, когда существуют такие целые х и у, что

6.56. Теорема. Если простое и то тогда и только тогда, когда существуют такие целые х и у, что

Доказательства этих теорем даны Холлом [1967] и Сторером [1967].