числа a: a0 = 1,a1,a2,a3,… В соответствии с теоремой Эйлера существует целое положительное число s, такое, что
as º 1 mod m. ( 1 )
В самой теореме s = j (m). Могут существовать и другие целые
положительные числа s, удовлетворяющие этому сравнению. Наименьшее из них обозначается e и называется показателем числа a по модулю m. Иногда e называют порядком числа a по модулю m.
Набор степеней числа a вида: a0,a1,a2,a3,…,ae-1 попарно несравнимы между собой по модулю m. Докажем это. Пусть, например, при некоторых n1 и n2 выполняется сравнение:
an1 º an2 mod m, где для определенности n1 < n2 < e. Умножим обе части сравнения на ae-n2, тогда получим: a (e+n1-n2) º 1 mod m. Но поскольку n1<n2, то в левой части сравнения степень числа a меньше e, что противоречит тому, что e – наименьшее число, удовлетворяющее сравнению ( 1 ).
Если найдется некоторое k, такое, что ak º 1 mod m, то e является делителем k. Очевидно, что всегда e является делителем j (m).
Пример.
Возьмем m = 45, a = 2, (45,2) = 1. Функция Эйлера j (45) = 24, Следовательно, 224 º 1 mod 45. Число 24 представляется в канонической форма в виде: 24 = 233, т.е. имеет 8 разных делителей: 1,2,3,4,6,8,12,24. Проверка показывает, что наименьшее число e = 12, так как 212 º 1 mod 45.
Если показатель e числа a по модулю m равен j (m), то a называют примитивным элементом по модулю m.
Пример. По каким модулям число a = 2 является примитивным
элементом ?
m = 3, 5, 7, 9 ,11, 15, 17, 19.