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

В теории чисел , учитывая целое положительное число n и целое число , взаимно простое с n , мультипликативный порядок числа n — по модулю это наименьшее целое положительное число k такое, что ${\textstyle a^{k}\ \equiv \ 1{\pmod {n}}}$.

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

Порядок по n модулю иногда записывают как $\operatorname {ord} _{n}(a)$.

Пример

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

${\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}}\\\vdots \end{array}}$

Наименьшее целое положительное число k такое, что 4 ^к ≡ 1 (по модулю 7) равно 3, поэтому порядок 4 (по модулю 7) равен 3.

Свойства

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

Понятие мультипликативного порядка является частным случаем порядка элементов группы . Мультипликативный порядок числа a по модулю n — это порядок числа a в мультипликативной группе , элементами которой являются остатки по модулю n чисел, взаимно простых с n , и групповая операция которой — умножение по модулю n . Это единиц кольца ​ Zn _; группа он имеет φ ( n ) элементов, φ — это Эйлера и обозначается как U ( n ) или U ( Zn _{функция} ).

Как следствие теоремы Лагранжа , порядок a (mod n ) всегда делит φ ( n ). Если порядок a на самом деле равен φ ( n ) и, следовательно, максимально велик, то a называется примитивным корнем по модулю n . Это означает, что группа U ( n ) циклическая и класс вычетов a порождает ее.

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

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

• Максима CAS : zn_order (a, n)
• Язык Wolfram : MultiplicativeOrder[k, n]
• Розеттский кодекс - примеры мультипликативного порядка на разных языках

См. также

• Дискретный логарифм
• Модульная арифметика

Ссылки

• Нивен, Иван ; Цукерман, Герберт С.; Монтгомери, Хью Л. (1991). Введение в теорию чисел (5-е изд.). Джон Уайли и сыновья . ISBN  0-471-62546-9 .

Внешние ссылки

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