Мультипликативный порядок

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

$a^\ell \equiv 1\pmod m.$

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

Пример

Так как $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.

См. также

• Дискретное логарифмирование
• Функция Кармайкла