Введение

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

Порядок a по модулю n иногда записывается как .

Свойства

Даже не зная, что мы работаем в мультипликативной группе целых чисел по модулю n, мы можем показать, что a действительно имеет порядок, заметив, что степени a могут принимать только конечное число различных значений по модулю n, поэтому, согласно принципу Дирихле, должны существовать две степени, скажем, s и t, и без потери общности s > t, такие что as ≡ at (mod n). Поскольку a и n взаимно просты, a имеет обратный элемент a−1, и мы можем умножить обе стороны конгруэнтности на a−t, получив as−t ≡ 1 (mod 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).