Показатель числа по модулю

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

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

Свойства



  • ab(modm)P(a)=P(b), поэтому можно считать, что показатель задан на классе вычетов a¯ по модулю m.
  • an1(modm)P(a)n. В частности, P(a)λ(m) и P(a)φ(m), где λ(m) — функция Кармайкла, а φ(m) — функция Эйлера.
  • atas(modm)ts(modP(a)).
  • P(as)P(a); если gcd(s,P(a))=1, то P(as)=P(a).
  • Если p — простое число и P(a)=k, то a,,ak — все решения сравнения xk1(modp).
  • Если p — простое число, то P(a)=p1a — образующая группы Zp.
  • Если ψ(k) — количество классов вычетов с показателем k, то kφ(m)ψ(k)=φ(m). А для простых модулей даже ψ(k)=φ(k).
  • Если p — простое число, то группа вычетов Zp× циклична и потому, если a=gdk, где g — образующая, dp1, а k — взаимно просто с p1, то P(a)=p1d. В общем случае для произвольного модуля m можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов Zm×.

Пример


 Так как 241(mod15), но 211(mod15),221(mod15), 231(mod15), то порядок числа2 по модулю 15 равен 4.

Вычисление


 Если известно разложение модуля m на простые множители pj иизвестно разложение чисел pj1 на простые множители, то показательзаданного числа a может быть найден за полиномиальное время отlnm. Для вычисления достаточно найти разложение на множители функцииКармайкла λ(m) и вычислить все admodm для всехdλ(m). Поскольку число делителей ограничено многочленом отlnm, а возведение в степень по модулю происходит за полиномиальноевремя, то алгоритм поиска будет полиномиальным.

Приложения


ХарактерыДирихле


 Характер Дирихле χ по модулю m определяется обязательнымисоотношениями χ(ab)=χ(a)χ(b) и χ(a)=χ(a+m). Чтобы этисоотношения выполнялись, необходимо, чтобы χ(a) был равенкакому-либо комплексному корню из единицы степени Pm(a).