В модульных арифметиках, что целые числа взаимно простые (взаимно простые) с п из множества из п неотрицательных целых чисел образуют группу относительно умножения по модулю п, называются мультипликативной группа целых чисел по модулю п. Эквивалентно, элементы этой группы можно рассматривать как классы конгруэнции, также известные как вычеты по модулю n, которые взаимно просты с n. Следовательно, другое название - группа примитивных классов вычетов по модулю n. В теории колец, ветви абстрактной алгебры, она описывается как группа единиц кольца целых чисел по модулю n. Здесь единицы относятся к элементам с мультипликативным обратным, которые в этом кольце в точности взаимно просты с n.
Алгебраическая структура → Теория групп Теория групп | ||||
---|---|---|---|---|
Основные понятия
| ||||
Конечные группы
| ||||
Модульные группы
| ||||
Топологические группы и группы Ли
| ||||
Алгебраические группы | ||||
|
Эта фактор-группа, обычно обозначаемая, является фундаментальной в теории чисел. Он нашел применение в криптографии, целочисленной факторизации и проверке простоты. Это абелева, конечная группа, порядок задается Функция Эйлера : Для простой п группа является циклической, и в целом структура легко описать, хотя даже для простого п нет общей формулы для нахождения генераторов известно.
Это несложное упражнение, чтобы показать, что при умножении множество классов конгруэнции по модулю n, взаимно простых с n, удовлетворяет аксиомам абелевой группы.
В самом деле, a взаимно просто с n тогда и только тогда, когда gcd ( a, n) = 1. Целые числа в том же классе сравнения a ≡ b (mod n) удовлетворяют gcd ( a, n) = gcd ( b, n), следовательно, одно взаимно просто с n тогда и только тогда, когда другое является. Таким образом, понятие классов сравнения по модулю n, взаимно простых с n, определено правильно.
Поскольку gcd ( a, n) = 1 и gcd ( b, n) = 1 влечет gcd ( ab, n) = 1, множество классов, взаимно простых с n, замкнуто относительно умножения.
Целочисленное умножение учитывает классы сравнения, то есть a ≡ a ' и b ≡ b' (mod n) влечет ab ≡ a'b ' (mod n). Это означает, что умножение ассоциативно, коммутативно и что класс 1 является единственной мультипликативной единицей.
Наконец, с учетом более, то мультипликативный обратный из более по модулю п представляет собой целое число х, удовлетворяющее ах ≡ 1 ( по модулю п). Он существует именно тогда, когда 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. Он задается функцией totient Эйлера : (последовательность A000010 в OEIS ). Для простого р,.
Группа является циклической тогда и только тогда, когда n равно 1, 2, 4, p k или 2 p k, где p - нечетное простое число и k gt; 0. Для всех остальных значений n группа не является циклической. Впервые это доказал Гаусс.
Это означает, что для этих n:
По определению группа является циклической тогда и только тогда, когда она имеет генератор g ( порождающий набор { g } размера один), то есть степени дают все возможные вычеты по модулю n, взаимно простые с n (первые степени дают каждому ровно один раз). Генератор называется первообразным корнем по модулю n. Если есть генератор, то их есть.
По модулю 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, верен для старших степеней 2 k, k gt; 2: это 2-торсионная подгруппа (поэтому не является циклической), а степени 3 являются циклической подгруппой порядка 2 k - 2, поэтому
По основной теореме о конечных абелевых группах группа изоморфна прямому произведению циклических групп степенных порядков простых чисел.
В частности, китайская теорема об остатках гласит, что если тогда кольцо является прямым произведением колец, соответствующих каждому из его простых факторов мощности:
Точно так же группа единиц является прямым произведением групп, соответствующих каждому из основных факторов мощности:
Для каждой нечетной степени простого числа соответствующий множитель представляет собой циклическую группу порядка, которая может дополнительно разлагаться на циклические группы порядков степени простого числа. Для степеней двойки множитель не является циклическим, если k = 0, 1, 2, но делится на циклические группы, как описано выше.
Порядок группы - это произведение порядков циклических групп в прямом произведении. Показатель в группе, то есть наименьшее общее кратное порядков в циклических групп, задается функцией Carmichael (последовательность A002322 в OEIS ). Другими словами, это наименьшее число такое, что для каждого в копервичных к п, имеет место. Он делится и равен ему тогда и только тогда, когда группа циклическая.
Если n составное, существует подгруппа мультипликативной группы, называемая «группой лжесвидетелей», в которой элементы, возведенные в степень n - 1, сравнимы с 1 по модулю n. (Поскольку вычет 1 при возведении в любую степень сравним с 1 по модулю n, множество таких элементов непусто.) Из-за Маленькой теоремы Ферма можно сказать, что такие вычеты являются «ложными срабатываниями» или «ложными свидетелями» для первобытность п. Число 2 - это остаток, наиболее часто используемый в этой базовой проверке на простоту, поэтому 341 = 11 × 31 известен, поскольку 2 340 сравнимо с 1 по модулю 341, а 341 - наименьшее такое составное число (относительно 2). Для 341 подгруппа ложных свидетелей содержит 100 остатков и, следовательно, имеет индекс 3 внутри мультипликативной группы из 300 элементов по модулю 341.
Самый маленький пример с нетривиальной подгруппой лжесвидетелей - 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, так как при этих значениях х, х 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 равны
Генераторная установка | Генераторная установка | Генераторная установка | Генераторная установка | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | C 1 | 1 | 1 | 0 | 33 | С 2 × С 10 | 20 | 10 | 2, 10 | 65 | С 4 × С 12 | 48 | 12 | 2, 12 | 97 | С 96 | 96 | 96 | 5 | |||
2 | C 1 | 1 | 1 | 1 | 34 | С 16 | 16 | 16 | 3 | 66 | С 2 × С 10 | 20 | 10 | 5, 7 | 98 | С 42 | 42 | 42 | 3 | |||
3 | C 2 | 2 | 2 | 2 | 35 год | С 2 × С 12 | 24 | 12 | 2, 6 | 67 | С 66 | 66 | 66 | 2 | 99 | С 2 × С 30 | 60 | 30 | 2, 5 | |||
4 | C 2 | 2 | 2 | 3 | 36 | С 2 × С 6 | 12 | 6 | 5, 19 | 68 | С 2 × С 16 | 32 | 16 | 3, 67 | 100 | С 2 × С 20 | 40 | 20 | 3, 99 | |||
5 | C 4 | 4 | 4 | 2 | 37 | С 36 | 36 | 36 | 2 | 69 | С 2 × С 22 | 44 год | 22 | 2, 68 | 101 | С 100 | 100 | 100 | 2 | |||
6 | C 2 | 2 | 2 | 5 | 38 | С 18 | 18 | 18 | 3 | 70 | С 2 × С 12 | 24 | 12 | 3, 69 | 102 | С 2 × С 16 | 32 | 16 | 5, 101 | |||
7 | С 6 | 6 | 6 | 3 | 39 | С 2 × С 12 | 24 | 12 | 2, 38 | 71 | С 70 | 70 | 70 | 7 | 103 | С 102 | 102 | 102 | 5 | |||
8 | С 2 × С 2 | 4 | 2 | 3, 5 | 40 | С 2 × С 2 × С 4 | 16 | 4 | 3, 11, 39 | 72 | С 2 × С 2 × С 6 | 24 | 6 | 5, 17, 19 | 104 | С 2 × С 2 × С 12 | 48 | 12 | 3, 5, 103 | |||
9 | С 6 | 6 | 6 | 2 | 41 год | С 40 | 40 | 40 | 6 | 73 | С 72 | 72 | 72 | 5 | 105 | С 2 × С 2 × С 12 | 48 | 12 | 2, 29, 41 | |||
10 | C 4 | 4 | 4 | 3 | 42 | С 2 × С 6 | 12 | 6 | 5, 13 | 74 | С 36 | 36 | 36 | 5 | 106 | С 52 | 52 | 52 | 3 | |||
11 | С 10 | 10 | 10 | 2 | 43 год | С 42 | 42 | 42 | 3 | 75 | С 2 × С 20 | 40 | 20 | 2, 74 | 107 | С 106 | 106 | 106 | 2 | |||
12 | С 2 × С 2 | 4 | 2 | 5, 7 | 44 год | С 2 × С 10 | 20 | 10 | 3, 43 | 76 | С 2 × С 18 | 36 | 18 | 3, 37 | 108 | С 2 × С 18 | 36 | 18 | 5, 107 | |||
13 | С 12 | 12 | 12 | 2 | 45 | С 2 × С 12 | 24 | 12 | 2, 44 | 77 | С 2 × С 30 | 60 | 30 | 2, 76 | 109 | С 108 | 108 | 108 | 6 | |||
14 | С 6 | 6 | 6 | 3 | 46 | С 22 | 22 | 22 | 5 | 78 | С 2 × С 12 | 24 | 12 | 5, 7 | 110 | С 2 × С 20 | 40 | 20 | 3, 109 | |||
15 | С 2 × С 4 | 8 | 4 | 2, 14 | 47 | С 46 | 46 | 46 | 5 | 79 | С 78 | 78 | 78 | 3 | 111 | С 2 × С 36 | 72 | 36 | 2, 110 | |||
16 | С 2 × С 4 | 8 | 4 | 3, 15 | 48 | С 2 × С 2 × С 4 | 16 | 4 | 5, 7, 47 | 80 | С 2 × С 4 × С 4 | 32 | 4 | 3, 7, 79 | 112 | С 2 × С 2 × С 12 | 48 | 12 | 3, 5, 111 | |||
17 | С 16 | 16 | 16 | 3 | 49 | С 42 | 42 | 42 | 3 | 81 год | С 54 | 54 | 54 | 2 | 113 | С 112 | 112 | 112 | 3 | |||
18 | С 6 | 6 | 6 | 5 | 50 | С 20 | 20 | 20 | 3 | 82 | С 40 | 40 | 40 | 7 | 114 | С 2 × С 18 | 36 | 18 | 5, 37 | |||
19 | С 18 | 18 | 18 | 2 | 51 | С 2 × С 16 | 32 | 16 | 5, 50 | 83 | С 82 | 82 | 82 | 2 | 115 | С 2 × С 44 | 88 | 44 год | 2, 114 | |||
20 | С 2 × С 4 | 8 | 4 | 3, 19 | 52 | С 2 × С 12 | 24 | 12 | 7, 51 | 84 | С 2 × С 2 × С 6 | 24 | 6 | 5, 11, 13 | 116 | С 2 × С 28 | 56 | 28 год | 3, 115 | |||
21 год | С 2 × С 6 | 12 | 6 | 2, 20 | 53 | С 52 | 52 | 52 | 2 | 85 | С 4 × С 16 | 64 | 16 | 2, 3 | 117 | С 6 × С 12 | 72 | 12 | 2, 17 | |||
22 | С 10 | 10 | 10 | 7 | 54 | С 18 | 18 | 18 | 5 | 86 | С 42 | 42 | 42 | 3 | 118 | С 58 | 58 | 58 | 11 | |||
23 | С 22 | 22 | 22 | 5 | 55 | С 2 × С 20 | 40 | 20 | 2, 21 | 87 | С 2 × С 28 | 56 | 28 год | 2, 86 | 119 | С 2 × С 48 | 96 | 48 | 3, 118 | |||
24 | С 2 × С 2 × С 2 | 8 | 2 | 5, 7, 13 | 56 | С 2 × С 2 × С 6 | 24 | 6 | 3, 13, 29 | 88 | С 2 × С 2 × С 10 | 40 | 10 | 3, 5, 7 | 120 | С 2 × С 2 × С 2 × С 4 | 32 | 4 | 7, 11, 19, 29 | |||
25 | С 20 | 20 | 20 | 2 | 57 год | С 2 × С 18 | 36 | 18 | 2, 20 | 89 | С 88 | 88 | 88 | 3 | 121 | С 110 | 110 | 110 | 2 | |||
26 год | С 12 | 12 | 12 | 7 | 58 | С 28 | 28 год | 28 год | 3 | 90 | С 2 × С 12 | 24 | 12 | 7, 11 | 122 | С 60 | 60 | 60 | 7 | |||
27 | С 18 | 18 | 18 | 2 | 59 | С 58 | 58 | 58 | 2 | 91 | С 6 × С 12 | 72 | 12 | 2, 3 | 123 | С 2 × С 40 | 80 | 40 | 7, 83 | |||
28 год | С 2 × С 6 | 12 | 6 | 3, 13 | 60 | С 2 × С 2 × С 4 | 16 | 4 | 7, 11, 19 | 92 | С 2 × С 22 | 44 год | 22 | 3, 91 | 124 | С 2 × С 30 | 60 | 30 | 3, 61 | |||
29 | С 28 | 28 год | 28 год | 2 | 61 | С 60 | 60 | 60 | 2 | 93 | С 2 × С 30 | 60 | 30 | 11, 61 | 125 | С 100 | 100 | 100 | 2 | |||
30 | С 2 × С 4 | 8 | 4 | 7, 11 | 62 | С 30 | 30 | 30 | 3 | 94 | С 46 | 46 | 46 | 5 | 126 | С 6 × С 6 | 36 | 6 | 5, 13 | |||
31 год | С 30 | 30 | 30 | 3 | 63 | С 6 × С 6 | 36 | 6 | 2, 5 | 95 | С 2 × С 36 | 72 | 36 | 2, 94 | 127 | С 126 | 126 | 126 | 3 | |||
32 | С 2 × С 8 | 16 | 8 | 3, 31 | 64 | С 2 × С 16 | 32 | 16 | 3, 63 | 96 | С 2 × С 2 × С 8 | 32 | 8 | 5, 17, 31 | 128 | С 2 × С 32 | 64 | 32 | 3, 127 |
Disquisitiones Arithmeticae был переведен из Гаусса Цицерона латыни в английском и немецком языках. Немецкое издание включает все его работы по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.