Показать меню

Порядок числа по модулю

18.12.2020
23

Показателем, или мультипликативным порядком, целого числа 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)} .

Еще по этой теме:
Эйлеровы числа
05:09, 18 декабрь
Эйлеровы числа
Эйлеровы числа (или числа Эйлера) — целые числа E 0 , E 1
Кольцо множеств
14:43, 17 декабрь
Кольцо множеств
Кольцо множеств — непустая система множеств R {displaystyle R} , замкнутая относительно пересечения и симметрической разности конечного числа элементов. Это
Цепь Каннингема
11:22, 17 декабрь
Цепь Каннингема
Цепь Каннингема (цепь почти удвоенных чисел) — последовательность простых чисел определённого вида, названо в честь математика Алана Каннингема. Цепь Каннингема первого рода длины n — это
Существенно особая точка
14:44, 12 декабрь
Существенно особая точка
Изолированная особая точка z 0 {displaystyle z_{0}} функции f (
Максимальный тор
12:52, 03 декабрь
Максимальный тор
Максимальный тор связной вещественной группы Ли G {displaystyle G} — связная компактная коммутативная подгруппа Ли T
Обратный элемент
23:38, 01 декабрь
Обратный элемент
Обратный элемент — термин в общей алгебре, обобщающий понятия обратного числа (для умножения) и противоположного числа (для сложения). Определения Пусть ( M
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent