В теории чисел, учитывая положительное целое число п и целое число копервичной к п, тем мультипликативный порядок из более по модулю п является наименьшим положительным целым числом к таким образом, что.
Другими словами, мультипликативный порядок в по модулю п есть порядок из в мультипликативной группе из звеньев в кольце целых чисел по модулю п.
Порядок в по модулю п иногда записывается в виде.
Степени 4 по модулю 7 следующие:
Наименьшее натуральное число k такое, что 4 k ≡ 1 (mod 7) равно 3, поэтому порядок 4 (mod 7) равен 3.
Даже не зная, что мы работаем в мультипликативной группе целых чисел по модулю n, мы можем показать, что a на самом деле имеет порядок, отметив, что степени a могут принимать только конечное число различных значений по модулю n, поэтому в соответствии с принципом ячейки должно быть две силы, скажем s и т и без ограничения общности, с gt; т, так что в ы ≡ в т ( по модулю п). Так как и п являются взаимно просты, то это означает, что имеет обратный элемент -1, и мы можем умножить обе стороны конгруэнции с в -т, получа через S -T ≡ 1 ( по модулю п).
Понятие мультипликативного порядка - это частный случай порядка элементов группы. Мультипликативный порядок числа a по модулю n - это порядок числа a в мультипликативной группе, элементы которой являются вычетами по модулю n чисел, взаимно простых с n, а групповая операция - это умножение по модулю n. Это группа единиц в кольце Z п ; он имеет φ ( n) элементов, φ - функция Эйлера, и обозначается как U ( n) или U ( Z n).
Как следствие теоремы Лагранжа, порядок a (mod n) всегда делит φ ( n). Если порядок a на самом деле равен φ ( n) и, следовательно, настолько велик, насколько это возможно, то a называется первообразным корнем по модулю n. Это означает, что группа U ( n) циклическая и класс вычетов a порождает ее.
Порядок a (mod n) также делит λ ( n), значение функции Кармайкла, что является даже более сильным утверждением, чем делимость φ ( n).