Как найти порядок числа по модулю

Показателем, или мультипликативным порядком, целого числа a {displaystyle a} по модулю m {displaystyle m} называется наименьшее положительное целое число ℓ {displaystyle ell } , такое, что

a ℓ ≡ 1 ( mod m ) . {displaystyle a^{ell }equiv 1{pmod {m}}.}

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

Чтобы показать зависимость показателя ℓ {displaystyle ell } от a {displaystyle a} и m {displaystyle m} , его также обозначают P m ( a ) {displaystyle P_{m}(a)} , а если m {displaystyle m} фиксировано, то просто P ( a ) {displaystyle P(a)} .

Свойства

• a ≡ b ( mod m ) ⇒ P ( a ) = P ( b ) {displaystyle aequiv b{pmod {m}}Rightarrow P(a)=P(b)} , поэтому можно считать, что показатель задан на классе вычетов a ¯ {displaystyle {ar {a}}} по модулю m {displaystyle m} .
• a n ≡ 1 ( mod m ) ⇒ P ( a ) ∣ n {displaystyle a^{n}equiv 1{pmod {m}}Rightarrow P(a)mid n} . В частности, P ( a ) ∣ λ ( m ) {displaystyle P(a)mid lambda (m)} и P ( a ) ∣ φ ( m ) {displaystyle P(a)mid varphi (m)} , где λ ( m ) {displaystyle lambda (m)} — функция Кармайкла, а φ ( m ) {displaystyle varphi (m)} — функция Эйлера.
• a t ≡ a s ( mod m ) ⇔ t ≡ s ( mod P ( a ) ) . {displaystyle a^{t}equiv a^{s}{pmod {m}}Leftrightarrow tequiv s{pmod {P(a)}}.}
• P ( a s ) ∣ P ( a ) {displaystyle P(a^{s})mid P(a)} ; если gcd ( s , P ( a ) ) = 1 {displaystyle gcd(s,P(a))=1} , то P ( a s ) = P ( a ) . {displaystyle P(a^{s})=P(a).}
• Если p {displaystyle p} — простое число и P ( a ) = k {displaystyle P(a)=k} , то a , … , a k {displaystyle a,;ldots ,;a^{k}} — все решения сравнения x k ≡ 1 ( mod p ) {displaystyle x^{k}equiv 1{pmod {p}}} .
• Если p {displaystyle p} — простое число, то P ( a ) = p − 1 ⇔ a {displaystyle P(a)=p-1Leftrightarrow a} — образующая группы Z p {displaystyle mathbb {Z} _{p}} .
• Если ψ ( k ) {displaystyle psi (k)} — количество классов вычетов с показателем k {displaystyle k} , то ∑ k ∣ φ ( m ) ψ ( k ) = φ ( m ) {displaystyle sum limits _{k,mid ,varphi (m)}psi (k)=varphi (m)} . А для простых модулей даже ψ ( k ) = φ ( k ) {displaystyle psi (k)=varphi (k)} .
• Если p {displaystyle p} — простое число, то группа вычетов Z p × {displaystyle mathbb {Z} _{p}^{ imes }} циклична и потому, если a = g d k {displaystyle a=g^{dk}} , где g {displaystyle g} — образующая, d ∣ p − 1 {displaystyle dmid p-1} , а k {displaystyle k} — взаимно просто с p − 1 {displaystyle p-1} , то P ( a ) = p − 1 d {displaystyle P(a)={frac {p-1}{d}}} . В общем случае для произвольного модуля m {displaystyle m} можно вывести аналогичную формулу, пользуясь теоремой о структуре мультипликативной группы вычетов Z m × {displaystyle mathbb {Z} _{m}^{ imes }} .

Пример

Так как 2 4 ≡ 1 ( mod 15 ) {displaystyle 2^{4}equiv 1{pmod {15}}} , но 2 1 ≢ 1 ( mod 15 ) {displaystyle 2^{1}
ot equiv 1{pmod {15}}} , 2 2 ≢ 1 ( mod 15 ) {displaystyle 2^{2}
ot equiv 1{pmod {15}}} , 2 3 ≢ 1 ( mod 15 ) {displaystyle 2^{3}
ot equiv 1{pmod {15}}} , то порядок числа 2 по модулю 15 равен 4.

Вычисление

Если известно разложение модуля m {displaystyle m} на простые множители p j {displaystyle p_{j}} и известно разложение чисел p j − 1 {displaystyle p_{j}-1} на простые множители, то показатель заданного числа a {displaystyle a} может быть найден за полиномиальное время от ln ⁡ m {displaystyle ln m} . Для вычисления достаточно найти разложение на множители функции Кармайкла λ ( m ) {displaystyle lambda (m)} и вычислить все a d mod m {displaystyle a^{d}mod m} для всех d ∣ λ ( m ) {displaystyle dmid lambda (m)} . Поскольку число делителей ограничено многочленом от ln ⁡ m {displaystyle ln m} , а возведение в степень по модулю происходит за полиномиальное время, то алгоритм поиска будет полиномиальным.

Приложения

Характеры Дирихле

Характер Дирихле χ {displaystyle chi } по модулю m {displaystyle m} определяется обязательными соотношениями χ ( a b ) = χ ( a ) χ ( b ) {displaystyle chi (ab)=chi (a)chi (b)} и χ ( a ) = χ ( a + m ) {displaystyle chi (a)=chi (a+m)} . Чтобы эти соотношения выполнялись, необходимо, чтобы χ ( a ) {displaystyle chi (a)} был равен какому-либо комплексному корню из единицы степени P m ( a ) {displaystyle P_{m}(a)} .