Порядок числа по модулю
Показателем, или мультипликативным порядком, целого числа по модулю называется наименьшее положительное целое число , такое, что[1][2]
Показатель определен только для чисел , взаимно простых с модулем , то есть для элементов группы обратимых элементов кольца вычетов по модулю . При этом, если показатель числа по модулю определен, то он является делителем значения функции Эйлера (следствие теоремы Лагранжа) и значения функции Кармайкла .
Чтобы показать зависимость показателя от и , его также обозначают , а если фиксировано, то просто .
Свойства[править | править код]
- , поэтому можно считать, что показатель задан на классе вычетов по модулю .
- . В частности, и , где — функция Кармайкла, а — функция Эйлера.
- ; если , то
- Если — простое число и , то — все решения сравнения .
- Если — простое число, то — образующая группы .
- Если — количество классов вычетов с показателем , то . А для простых модулей даже .
- Если — простое число, то группа вычетов циклична и потому, если , где — образующая, , а — взаимно просто с , то . В общем случае для произвольного модуля можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов .
Пример[править | править код]
Так как , но , , , то порядок числа 2 по модулю 15 равен 4.
Вычисление[править | править код]
Если известно разложение модуля на простые множители и известно разложение чисел на простые множители, то показатель заданного числа может быть найден за полиномиальное время от . Для вычисления достаточно найти разложение на множители функции Кармайкла и вычислить все для всех . Поскольку число делителей ограничено многочленом от , а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.
Приложения[править | править код]
Характеры Дирихле[править | править код]
Характер Дирихле по модулю определяется обязательными соотношениями и . Чтобы эти соотношения выполнялись, необходимо, чтобы был равен какому-либо комплексному корню из единицы степени .
См. также[править | править код]
Примечания[править | править код]
- ↑ Бухштаб, 1966, с. 140.
- ↑ Виноградов, 1972, с. 92.
Литература[править | править код]
- Бухштаб А. А. Теория чисел. — М.: Просвещение, 1966.
- Виноградов И. М. Основы теории чисел. — М.: Наука, 1972.