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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

a^\ell \equiv 1\pmod m.

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

Чтобы показать зависимость показателя \ell от a и m, его также обозначают P_m(a), а если m фиксировано, то просто P(a).

Свойства[править | править вики-текст]

  • a\equiv b\pmod m\Rightarrow P(a)=P(b), поэтому можно считать, что показатель задан на классе вычетов \bar{a} по модулю m.
  • a^n\equiv 1\pmod m\Rightarrow P(a)\mid n. В частности, P(a)\mid\lambda(m) и P(a)\mid\varphi(m), где \lambda(m)функция Кармайкла, а \varphi(m)функция Эйлера.
  • a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.
  • P(a^s)\mid P(a); если \gcd(s,P(a))=1, то P(a^s)=P(a).
  • Если p — простое число и P(a)=k, то a,\ldots,a^k — все решения сравнения x^k\equiv 1\pmod p.
  • Если p — простое число, то P(a)=p-1\Leftrightarrow aобразующая группы \mathbb{Z}_p.
  • Если \psi(k) — количество классов вычетов с показателем k, то \sum\limits_{k\mid\varphi(m)}\psi(k)=\varphi(m). А для простых модулей даже \psi(k)=\varphi(k).
  • Если p — простое число, то группа вычетов \mathbb{Z}_p^{\times} циклична и потому, если a=g^{dk}, где g — образующая, d\mid p-1, а k взаимно просто с p-1, то P(a)=\frac{p-1}{d}. В общем случае для произвольного модуля m можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов\mathbb{Z}_m^{\times}.

Пример[править | править вики-текст]

Так как 2^4\equiv 1\pmod{15}, но 2^1\not\equiv 1\pmod{15}, 2^2\not\equiv 1\pmod{15}, 2^3\not\equiv 1\pmod{15}, то порядок числа 2 по модулю 15 равен 4.

Вычисление[править | править вики-текст]

Если известно разложение модуля m на простые множители p_j и известно разложение чисел p_j-1 на простые множители, то показатель заданного числа a может быть найден за полиномиальное время от \ln m. Для вычисления достаточно найти разложение на множители функции Кармайкла \lambda(m) и вычислить все a^d \mod m для всех d\mid \lambda (m). Поскольку число делителей ограничено многочленом от \ln m, а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Бухштаб Теория чисел
  • Виноградов Теория чисел