Порядок числа по модулю

(перенаправлено с «Показатель числа по модулю»)

Показателем, или мультипликативным порядком, целого числа по модулю называется наименьшее положительное целое число , такое, что[1][2]

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

Чтобы показать зависимость показателя от и , его также обозначают , а если фиксировано, то просто .

Свойства править

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

Пример править

Так как  , но  ,  ,  , то порядок числа 2 по модулю 15 равен 4.

Вычисление править

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

Приложения править

Характеры Дирихле править

Характер Дирихле   по модулю   определяется обязательными соотношениями   и  . Чтобы эти соотношения выполнялись, необходимо, чтобы   был равен какому-либо комплексному корню из единицы степени  .

См. также править

Примечания править

Литература править

  • Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
  • Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.