Русская Википедия:Порядок числа по модулю
Показателем, или мультипликативным порядком, целого числа <math>a</math> по модулю <math>m</math> называется наименьшее положительное целое число <math>\ell</math>, такое, чтоШаблон:SfnШаблон:Sfn
- <math>a^\ell\equiv 1\pmod m.</math>
Показатель определен только для чисел <math>a</math>, взаимно простых с модулем <math>m</math>, то есть для элементов группы обратимых элементов кольца вычетов по модулю <math>m</math>. При этом, если показатель числа <math>a</math> по модулю <math>m</math> определен, то он является делителем значения функции Эйлера <math>\varphi(m)</math> (следствие теоремы Лагранжа) и значения функции Кармайкла <math>\lambda(m)</math>.
Чтобы показать зависимость показателя <math>\ell</math> от <math>a</math> и <math>m</math>, его также обозначают <math>P_m(a)</math>, а если <math>m</math> фиксировано, то просто <math>P(a)</math>.
Свойства
- <math>a\equiv b\pmod m\Rightarrow P(a)=P(b)</math>, поэтому можно считать, что показатель задан на классе вычетов <math>\bar{a}</math> по модулю <math>m</math>.
- <math>a^n\equiv 1\pmod m\Rightarrow P(a)\mid n</math>. В частности, <math>P(a)\mid\lambda(m)</math> и <math>P(a)\mid\varphi(m)</math>, где <math>\lambda(m)</math> — функция Кармайкла, а <math>\varphi(m)</math> — функция Эйлера.
- <math>a^t\equiv a^s\pmod m \Leftrightarrow t\equiv s\pmod{P(a)}.</math>
- <math>P(a^s)\mid P(a)</math>; если <math>\gcd(s,P(a))=1</math>, то <math>P(a^s)=P(a).</math>
- Если <math>p</math> — простое число и <math>P(a)=k</math>, то <math>a,\;\ldots,\;a^k</math> — все решения сравнения <math>x^k\equiv 1\pmod p</math>.
- Если <math>p</math> — простое число, то <math>P(a)=p-1\Leftrightarrow a</math> — образующая группы <math>\mathbb{Z}_p</math>.
- Если <math>\psi(k)</math> — количество классов вычетов с показателем <math>k</math>, то <math>\sum\limits_{k\,\mid\,\varphi(m)}\psi(k)=\varphi(m)</math>. А для простых модулей даже <math>\psi(k)=\varphi(k)</math>.
- Если <math>p</math> — простое число, то группа вычетов <math>\mathbb{Z}_p^{\times}</math> циклична и потому, если <math>a=g^{dk}</math>, где <math>g</math> — образующая, <math>d\mid p-1</math>, а <math>k</math> — взаимно просто с <math>p-1</math>, то <math>P(a)=\frac{p-1}{d}</math>. В общем случае для произвольного модуля <math>m</math> можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов <math>\mathbb{Z}_m^{\times}</math>.
Пример
Так как <math>2^4\equiv 1\pmod{15}</math>, но <math>2^1\not\equiv 1\pmod{15}</math>, <math>2^2\not\equiv 1\pmod{15}</math>, <math>2^3\not\equiv 1\pmod{15}</math>, то порядок числа 2 по модулю 15 равен 4.
Вычисление
Если известно разложение модуля <math>m</math> на простые множители <math>p_j</math> и известно разложение чисел <math>p_j-1</math> на простые множители, то показатель заданного числа <math>a</math> может быть найден за полиномиальное время от <math>\ln m</math>. Для вычисления достаточно найти разложение на множители функции Кармайкла <math>\lambda(m)</math> и вычислить все <math>a^d\mod m</math> для всех <math>d\mid\lambda(m)</math>. Поскольку число делителей ограничено многочленом от <math>\ln m</math>, а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.
Приложения
Характеры Дирихле
Характер Дирихле <math>\chi</math> по модулю <math>m</math> определяется обязательными соотношениями <math>\chi(ab)=\chi(a)\chi(b)</math> и <math>\chi(a)=\chi(a+m)</math>. Чтобы эти соотношения выполнялись, необходимо, чтобы <math>\chi(a)</math> был равен какому-либо комплексному корню из единицы степени <math>P_{m}(a)</math>.
См. также
Примечания
Литература
