В модульной арифметике целые числа , взаимно простые (относительно простые) с n из набора n неотрицательных целых чисел, образуют группу при умножении по модулю n , называемую мультипликативной группой целых чисел по модулю n . Эквивалентно, элементы этой группы можно рассматривать как классы конгруэнтности , также известные как остатки по модулю n , которые взаимно просты с n . Отсюда другое название — группа примитивных классов вычетов по модулю n . В теории колец , разделе абстрактной алгебры , она описывается как группа единиц кольца целых чисел по модулю 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' и b ≡ b' (mod n ) следует ab ≡ a'b' (mod n ) . Это означает, что умножение ассоциативно, коммутативно и что класс 1 является уникальным мультипликативным тождеством.
Наконец, для данного a мультипликативным обратным к модулю n является целое число x, удовлетворяющее условию ax ≡ 1 (mod n ) . Оно существует именно тогда, когда a взаимно просто с n , потому что в этом случае gcd( a , n ) = 1 и по лемме Безу существуют целые числа x и y , удовлетворяющие ax + ny = 1 . Обратите внимание, что уравнение ax + ny = 1 подразумевает, что x взаимно прост с n , поэтому мультипликативный обратный принадлежит группе.
Множество (классов сравнения) целых чисел по модулю n с операциями сложения и умножения представляет собой кольцо . Обозначается или (обозначение относится к частному целых чисел по модулю идеального или состоящего из кратных n ). За пределами теории чисел часто используются более простые обозначения , хотя их можно спутать с p -адическими целыми числами , когда n - простое число.
Мультипликативная группа целых чисел по модулю n , которая представляет собой группу единиц в этом кольце, может быть записана как (в зависимости от автора) (для немецкого Einheit , что переводится как единица ), или аналогичных обозначений. В этой статье используется
Обозначения относятся к циклической группе порядка n . Он изоморфен группе целых чисел по модулю n при сложении. Обратите внимание, что или может также относиться к добавляемой группе. Например, мультипликативная группа для простого числа p является циклической и, следовательно, изоморфной аддитивной группе , но изоморфизм не очевиден.
Порядок мультипликативной группы целых чисел по модулю n — это количество целых чисел, взаимно простых с n . Оно задается функцией тотента Эйлера : (последовательность A000010 в OEIS ). Для простого p , .
Группа является циклической тогда и только тогда, когда n равно 1 , 2, 4, pk или 2pk , где p — нечетное простое число и k > 0 . При всех остальных значениях n группа не является циклической. [1] [2] [3] Впервые это было доказано Гауссом . [4]
Это означает, что для этих n :
По определению группа является циклической тогда и только тогда, когда она имеет генератор g ( порождающий набор { g } размера один), то есть степени дают все возможные остатки по модулю n, взаимно простые с n (первые степени дают каждому ровно один раз ). Генератор называется примитивным корнем по модулю n . [5] Если есть какие-либо генераторы, то они есть.
По модулю 1 любые два целых числа конгруэнтны, т.е. существует только один класс конгруэнтности, [0], взаимно простой с 1. Следовательно, это тривиальная группа с φ(1) = 1 элементом. Из-за своей тривиальности случай сравнений по модулю 1 обычно игнорируется, и некоторые авторы предпочитают не включать случай n = 1 в формулировки теорем.
По модулю 2 существует только один взаимно простой класс конгруэнции [1], как и тривиальная группа .
По модулю 4 существуют два взаимно простых класса конгруэнтности, [1] и [3], поэтому циклическая группа состоит из двух элементов.
По модулю 8 существует четыре взаимно простых класса конгруэнтности: [1], [3], [5] и [7]. Квадрат каждого из них равен 1, поэтому четверная группа Клейна .
По модулю 16 существует восемь взаимно простых классов конгруэнтности [1], [3], [5], [7], [9], [11], [13] и [15]. является 2- крученной подгруппой (т. е. квадрат каждого элемента равен 1), поэтому не является циклической. Степени 3 являются подгруппой порядка 4, как и степени 5. Таким образом ,
Шаблон, показанный номерами 8 и 16, справедлив [6] для высших степеней 2 k , k > 2 : это 2-крученная подгруппа, поэтому не может быть циклической, а степени 3 являются циклической подгруппой порядка 2 k − 2 , поэтому :
По основной теореме о конечных абелевых группах группа изоморфна прямому произведению циклических групп простых степенных порядков.
Более конкретно, китайская теорема об остатках [7] гласит, что если тогда кольцо является прямым произведением колец, соответствующих каждому из его простых степенных множителей:
Аналогично, группа единиц является прямым произведением групп, соответствующих каждому из простых коэффициентов мощности:
Для каждой нечетной простой степени соответствующим фактором является циклическая группа порядка , которая может далее факторизоваться в циклические группы порядков простой степени. Для степеней 2 фактор не является циклическим, если только k = 0, 1, 2, а разлагается на циклические группы, как описано выше.
Порядок группы есть произведение порядков циклических групп в прямом произведении. Показатель группы, то есть наименьшее общее кратное порядков в циклических группах, задается функцией Кармайкла ( последовательность A002322 в OEIS ). Другими словами, это наименьшее число такое, что для каждого имеет место взаимно простое число с n . Оно делит и равно ему тогда и только тогда, когда группа циклическая.
Если n составное, существует собственная подгруппа , называемая «группой ложных свидетелей», состоящая из решений уравнения , элементы которых, возведенные в степень n - 1 , конгруэнтны 1 по модулю n . [8] Маленькая теорема Ферма утверждает, что для n = p простое число, эта группа состоит из всех ; таким образом, для составного n такие остатки x являются «ложноположительными» или «ложными свидетелями» простоты n . Число x = 2 чаще всего используется в этой базовой проверке на простоту, а n = 341 = 11 × 31 примечательно, поскольку , а n = 341 — наименьшее составное число, для которого x = 2 является ложным свидетельством простоты. Фактически подгруппа ложных свидетелей для 341 содержит 100 элементов и имеет индекс 3 внутри группы из 300 элементов .
Наименьший пример с нетривиальной подгруппой лжесвидетелей — 9 = 3×3 . Существует 6 остатков, взаимно простых с 9: 1, 2, 4, 5, 7, 8. Поскольку 8 конгруэнтно -1 по модулю 9 , отсюда следует, что 8 8 конгруэнтно 1 по модулю 9. Таким образом, 1 и 8 являются ложноположительными для «простота» числа 9 (поскольку 9 на самом деле не является простым числом). Фактически это единственные, поэтому подгруппа {1,8} — это подгруппа лжесвидетелей. Тот же аргумент показывает, что n − 1 является «лжесвидетелем» для любого нечётного составного n .
Для n = 91 (= 7×13) существуют остатки, взаимно простые с 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 по модулю 91.
n = 561 (= 3 × 11 × 17) является числом Кармайкла , таким образом, s 560 конгруэнтно 1 по модулю 561 для любого целого числа s , взаимно простого с 561. Подгруппа лжесвидетелей в этом случае не является собственной; это целая группа мультипликативных единиц по модулю 561, состоящая из 320 остатков.
В этой таблице показано циклическое разложение и порождающий набор для n ≤ 128. Разложение и порождающий набор не уникальны; например,
(но ). В таблице ниже перечислено кратчайшее разложение (среди них выбирается первое лексикографически - это гарантирует, что изоморфные группы перечислены с одинаковыми разложениями). Генераторный набор также выбирается как можно более коротким, и для n с примитивным корнем указывается наименьший примитивный корень по модулю n .
Например, возьмите . Тогда означает, что порядок группы равен 8 (т.е. существует 8 чисел меньше 20, взаимно простых с ним); означает, что порядок каждого элемента делит 4, то есть четвертая степень любого числа, взаимно простого с 20, равна 1 (по модулю 20). Набор {3,19} порождает группу, что означает, что каждый элемент имеет форму 3 a × 19 b (где a равно 0, 1, 2 или 3, поскольку элемент 3 имеет порядок 4, и аналогично b равен 0 или 1, поскольку элемент 19 имеет порядок 2).
Наименьший примитивный корень по модулю n равен (0, если корня не существует)
Числа элементов минимального порождающего набора по модулю n равны
« Disquisitiones Arithmeticae» переведена с цицероновской латыни Гаусса на английский и немецкий языки . Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности , определение знака суммы Гаусса , исследования биквадратичной взаимности и неопубликованные заметки.