WikiDer > Мультипликативный порядок

В теория чисел, учитывая целое число а и положительное целое число п совмещать к а, то мультипликативный порядок из а по модулю п это наименьшее положительное целое число k с

${ Displaystyle а ^ {к} эквив 1 { pmod {п}} ,}$

Другими словами, мультипликативный порядок а по модулю п это порядок из а в мультипликативная группа из единицы в звенеть целых чисел по модулю п.

Получатель чего-то а по модулю п обычно пишется как ${ displaystyle k = operatorname {ord} _ {n} (а)}$ или же ${ displaystyle k = O_ {n} (a).}$

Пример

Степени 4 по модулю 7 следующие:

${ displaystyle { begin {array} {llll} 4 ^ {0} & = 1 & = 0 times 7 + 1 & Equiv 1 { pmod {7}} 4 ^ {1} & = 4 & = 0 раз 7 + 4 & эквив 4 { pmod {7}} 4 ^ {2} & = 16 & = 2 раз 7 + 2 & эквив 2 { pmod {7}} 4 ^ {3} & = 64 & = 9 times 7 + 1 & Equiv 1 { pmod {7}} 4 ^ {4} & = 256 & = 36 times 7 + 4 & Equiv 4 { pmod {7}} 4 ^ { 5} & = 1024 & = 146 times 7 + 2 & Equiv 2 { pmod {7}} end {array}}}$

${ displaystyle , { text {и т. д.}}}$

Наименьшее положительное целое число k так что 4^k = 1 (mod 7) равно 3, поэтому О₇(4) = 3.

Характеристики

Даже не зная, что мы работаем в мультипликативная группа целых чисел по модулю n, мы можем показать, что а на самом деле имеет приказ, отмечая, что полномочия а может принимать только конечное число различных значений по модулю п, так что согласно принцип голубятни должно быть две силы, скажем s и т и не теряя общий смысл s > т, так что а^s ≡ а^т (модп). С а и п находятся совмещать, это означает, что а имеет обратный элемент а⁻¹ и мы можем умножить обе части сравнения на а^−т, уступая а^s−т ≡ 1 (модп).

Концепция мультипликативного порядка - это частный случай порядок элементов группы. Мультипликативный порядок числа а по модулю п это порядок а в мультипликативная группа элементы которого являются вычетами по модулю п чисел, взаимно простых с п, а групповая операция - умножение по модулюп. Это группа единиц из звенеть Z_п; она имеет φ(п) элементов, φ Функция Эйлера, и обозначается как U(п) или жеU(Z_п).

Как следствие Теорема Лагранжа, ord_п(а) всегда разделяет φ(п). Если ord_п(а) фактически равно φ(п), а значит, как можно больше, то а называется первобытный корень по модулю п. Это означает, что группа U(п) является циклический и класс остатков а генерирует Это.

Порядок ord_п а также делит λ (п), значение Функция Кармайкла, что является даже более сильным утверждением, чем делимостьφ(п).

Языки программирования

• Maxima CAS : zn_order (a, n)^[1]
• Розеттский код - примеры мультипликативного порядка на разных языках^[2]

Смотрите также

• Дискретный логарифм
• Модульная арифметика
• Порядок (теория групп)
• Отношение конгруэнтности (модульная арифметика)

Рекомендации

• Вайсштейн, Эрик В. «Мультипликативный порядок». MathWorld.