Якщо — кількість класів лишків із показником , то . А для простих модулів навіть .
Якщо p — просте число, то група лишків циклічна і тому, якщо , де g — твірна, , а k взаємно просте із , то . В загальному випадку для довільного модуля m можна вивести аналогічну формулу, користуючись теоремою про структуру мультиплікативної групи лишків.
Приклад
Оскільки , але , , , то порядок числа 2 за модулем 15 дорівнює 4.
Обчислення
Якщо відомий розклад модуля m на прості множники і відомий розклад чисел на прості множники, то показник заданого числа a може бути знайдений за поліноміальний час від . Для обчислення досить знайти розклад на множники функції Кармайкла і обчислити всі для всіх . Оскільки число дільників обмежене многочленом від , а піднесення до степеня за модулем відбувається за поліноміальний час, то алгоритм пошуку буде поліноміальним.
Застосування
Характери Діріхле
Характер Діріхле за модулем визначається обов'язковими співвідношеннями і . Щоб ці співвідношення виконувалися, необхідно, щоб дорівнював якомусь комплексному кореню із одиниці степеня .