Мультипликативный порядок - Multiplicative order

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

${\displaystyle a^{k}\ \equiv \ 1{\pmod {n}}\,}$

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

Получатель чего-то а по модулю п обычно пишется как ${\displaystyle k=\operatorname {ord} _{n}(a)}$ или же ${\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\times 7+4&\equiv 4{\pmod {7}}\\4^{2}&=16&=2\times 7+2&\equiv 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{etc...}}}$

Наименьшее положительное целое число 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]

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

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

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

1. Maxima 5.42.0 Руководство: zn_order
2. rosettacode.org - примеры мультипликативного порядка на разных языках

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