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