Группа единиц кольца целых чисел по модулю n

Введение

Группа единиц кольца целых чисел по модулю n. В модульной арифметике целые числа, взаимно простые с n, из множества n неотрицательных целых чисел образуют группу относительно умножения по модулю n, называемую мультипликативной группой целых чисел по модулю n. Эквивалентно, элементы этой группы можно рассматривать как классы вычетов, также известные как остатки по модулю n, взаимно простые с n. Следовательно, другое название – группа примитивных классов вычетов по модулю n. В теории колец, разделе абстрактной алгебры, она описывается как группа единиц кольца целых чисел по модулю n. Здесь единицы – это элементы, имеющие мультипликативный обратный, которые в этом кольце являются точно теми, что взаимно просты с n.

Эта фактор-группа, обычно обозначаемая (Z/nZ)*, фундаментальна в теории чисел. Она используется в криптографии, факторизации целых чисел и проверке простоты. Это абелева, конечная группа, порядок которой задается функцией Эйлера: φ(n). Для простого n группа циклическая, и в целом ее структуру легко описать, но простой общей формулы для нахождения образующих не существует.

Групповые аксиомы

Это простое упражнение, чтобы показать, что при умножении множество классов вычетов по модулю n, взаимно простых с n, удовлетворяет аксиомам для абелевой группы. Действительно, число a взаимно просто с n тогда и только тогда, когда НОД(a, n) = 1. Целые числа в одном и том же классе вычетов a ≡ b (mod n) удовлетворяют НОД(a, n) = НОД(b, n); следовательно, одно число взаимно просто с n тогда и только тогда, когда взаимно просто другое. Таким образом, понятие классов вычетов по модулю n, взаимно простых с n, корректно определено. Поскольку НОД(a, n) = 1 и НОД(b, n) = 1 влечет за собой НОД(ab, n) = 1, множество классов, взаимно простых с n, замкнуто относительно умножения. Умножение целых чисел сохраняет классы вычетов, то есть, если a ≡ a' (mod n) и b ≡ b' (mod n), то ab ≡ a'b' (mod n). Это означает, что умножение ассоциативно, коммутативно, и что класс 1 является единственным нейтральным элементом относительно умножения. Наконец, для заданного a, мультипликативный обратный к a по модулю n – это целое число x, удовлетворяющее ax ≡ 1 (mod n). Он существует ровно тогда, когда a взаимно просто с n, потому что в этом случае НОД(a, n) = 1 и по лемме Безу существует пара целых чисел x и y, удовлетворяющих ax + ny = 1. Заметьте, что уравнение ax + ny = 1 подразумевает, что x взаимно просто с n, следовательно, мультипликативный обратный принадлежит группе.

Обозначение

Множество (классов вычетов) целых чисел по модулю n с операциями сложения и умножения является кольцом. Оно обозначается или (обозначение относится к взятию фактор-группы целых чисел по модулю идеала или , состоящего из кратных n). Вне теории чисел часто используется более простое обозначение , хотя оно может бытьпутано с p-адическими числами, когда n – простое число. Мультипликативная группа целых чисел по модулю n, которая является группой обратимых элементов в этом кольце, может быть записана как (в зависимости от автора) (от немецкого Einheit, что переводится как "единица"), , или аналогичные обозначения. В данной статье используется обозначение .

Обозначение относится к циклической группе порядка n. Она изоморфна группе целых чисел по модулю n относительно сложения. Следует отметить, что или также могут обозначать группу относительно сложения. Например, мультипликативная группа для простого числа p циклична и, следовательно, изоморфна аддитивной группе , но изоморфизм не очевиден.

Структура

Порядок мультипликативной группы целых чисел по модулю n равен числу целых чисел, взаимно простых с n. Он задается функцией Эйлера: Для простого числа p, .

Подгруппа лжесвидетелей

Если n составное, существует собственная подгруппа группы мультипликаторов по модулю n, называемая "группой ложных свидетелей", состоящая из решений уравнения x^(n-1) ≡ 1 (mod n). Малая теорема Ферма утверждает, что для n = p, где p – простое число, эта группа состоит из всех элементов, отличных от единицы. Таким образом, для составного n такие остатки x являются "ложноположительными" или "ложными свидетелями" простоты n. Число x = 2 наиболее часто используется в этой базовой проверке простоты, и n = 341 = 11 × 31 примечательно тем, что 2^(340) ≡ 1 (mod 341), и n = 341 является наименьшим составным числом, для которого x = 2 является ложным свидетелем простоты. Фактически, подгруппа ложных свидетелей для 341 содержит 100 элементов и имеет индекс 3 в группе из 300 элементов.

n = 9

Самый маленький пример с нетривиальной подгруппой ложных свидетелей — 1=9 = 3 × 3. Существует 6 вычетов, взаимно простых с 9: 1, 2, 4, 5, 7, 8. Поскольку 8 сравнимо с −1 по модулю 9, следует, что 88 сравнимо с 1 по модулю 9. Таким образом, 1 и 8 являются ложными срабатываниями для "простоты" 9 (поскольку 9 на самом деле не является простым числом). Это, фактически, единственные такие случаи, поэтому подгруппа {1, 8} является подгруппой ложных свидетелей. Тот же аргумент показывает, что n − 1 является "ложным свидетелем" для любого нечётного составного числа n.

n = 91

Для n = 91 (= 7 × 13) существует φ(91) взаимно простых с 91 остатков, половина из них (то есть 36) являются ложными свидетелями для 91, а именно: 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88 и 90, поскольку для этих значений x выполняется сравнение x^90 ≡ 1 (mod 91).

n = 561

n = 561 (= 3 × 11 × 17) является числом Кармайкла, следовательно, s⁵⁶⁰ сравнимо с 1 по модулю 561 для любого целого числа s, взаимно простого с 561. Подгруппа ложных свидетелей в этом случае не является собственной; она представляет собой всю группу мультипликативных единиц по модулю 561, состоящую из 320 классов вычетов.