Мультипликативная группа целых чисел по модулю n

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

В модульной арифметике целые числа , взаимно простые (относительно простые) с n из набора n неотрицательных целых чисел, образуют группу при умножении по модулю n , называемую мультипликативной группой целых чисел по модулю n . Эквивалентно, элементы этой группы можно рассматривать как классы конгруэнтности , также известные как остатки по модулю n , которые взаимно просты с n . Отсюда другое название — группа примитивных классов вычетов по модулю n . В теории колец , разделе абстрактной алгебры , она описывается как группа единиц кольца целых чисел по модулю n . Здесь единицы относятся к элементам с мультипликативным обратным , которые в этом кольце являются в точности теми, которые взаимно просты с n . ${\displaystyle \{0,1,\dots ,n-1\}}$

Эта факторгруппа , которую обычно обозначают , является фундаментальной в теории чисел . Он используется в криптографии , факторизации целых чисел и тестировании на простоту . Это абелева конечная группа , порядок которой задается функцией тотента Эйлера : для простых чисел группа является циклической , и в целом структуру легко описать, но простая общая формула для поиска генераторов неизвестна. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (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 - простое число. ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /(n)}$ ${\displaystyle n\mathbb {Z} }$ ${\displaystyle (n)}$ ${\displaystyle \mathbb {Z} _{n}}$

Мультипликативная группа целых чисел по модулю n , которая представляет собой группу единиц в этом кольце, может быть записана как (в зависимости от автора)   (для немецкого Einheit , что переводится как единица ), или аналогичных обозначений. В этой статье используется ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$   ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}$   ${\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),}$   ${\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )}$ ${\displaystyle \mathbb {Z} _{n}^{*}}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

Обозначения относятся к циклической группе порядка n . Он изоморфен группе целых чисел по модулю n при сложении. Обратите внимание, что или может также относиться к добавляемой группе. Например, мультипликативная группа для простого числа p является циклической и, следовательно, изоморфной аддитивной группе , но изоморфизм не очевиден. ${\displaystyle \mathrm {C} _{n}}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} _{n}}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle \mathbb {Z} /(p-1)\mathbb {Z} }$

Состав

Порядок мультипликативной группы целых чисел по модулю n — это количество целых чисел, взаимно простых с n . Оно задается функцией тотента Эйлера : (последовательность A000010 в OEIS ). Для простого p , . ${\displaystyle \{0,1,\dots ,n-1\}}$ ${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n)}$ ${\displaystyle \varphi (p)=p-1}$

Циклический случай

Группа является циклической ^тогда и только тогда, когда n равно 1 ^, 2, 4, pk или 2pk , где p — нечетное простое число и k > 0 . При всех остальных значениях n группа не является циклической. ^{[1] [2] [3]} Впервые это было доказано Гауссом . ^[4] ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Это означает, что для этих n :

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \mathrm {C} _{\varphi (n)},}$где ${\displaystyle \varphi (p^{k})=\varphi (2p^{k})=p^{k}-p^{k-1}.}$

По определению группа является циклической тогда и только тогда, когда она имеет генератор g ( порождающий набор { g } размера один), то есть степени дают все возможные остатки по модулю n, взаимно простые с n (первые степени дают каждому ровно один раз ). Генератор называется примитивным корнем по модулю n . ^[5] Если есть какие-либо генераторы, то они есть. ${\displaystyle g^{0},g^{1},g^{2},\dots ,}$ ${\displaystyle \varphi (n)}$ ${\displaystyle g^{0},\dots ,g^{\varphi (n)-1}}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle \varphi (\varphi (n))}$

Полномочия 2

По модулю 1 любые два целых числа конгруэнтны, т.е. существует только один класс конгруэнтности, [0], взаимно простой с 1. Следовательно, это тривиальная группа с φ(1) = 1 элементом. Из-за своей тривиальности случай сравнений по модулю 1 обычно игнорируется, и некоторые авторы предпочитают не включать случай n = 1 в формулировки теорем. ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

По модулю 2 существует только один взаимно простой класс конгруэнции [1], как и тривиальная группа . ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong \mathrm {C} _{1}}$

По модулю 4 существуют два взаимно простых класса конгруэнтности, [1] и [3], поэтому циклическая группа состоит из двух элементов. ${\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong \mathrm {C} _{2},}$

По модулю 8 существует четыре взаимно простых класса конгруэнтности: [1], [3], [5] и [7]. Квадрат каждого из них равен 1, поэтому четверная группа Клейна . ${\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$

По модулю 16 существует восемь взаимно простых классов конгруэнтности [1], [3], [5], [7], [9], [11], [13] и [15]. является 2- крученной подгруппой (т. е. квадрат каждого элемента равен 1), поэтому не является циклической. Степени 3 являются подгруппой порядка 4, как и степени 5.   Таким образом , ${\displaystyle \{\pm 1,\pm 7\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}$ ${\displaystyle \{1,3,9,11\}}$ ${\displaystyle \{1,5,9,13\}.}$ ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{4}.}$

Шаблон, показанный номерами 8 и 16, справедлив ^[6] для высших степеней 2 ^k , k > 2 : это 2-крученная подгруппа, поэтому не может быть циклической, а степени 3 являются циклической подгруппой порядка 2 ^{k − 2} , поэтому : ${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong \mathrm {C} _{2}\times \mathrm {C} _{2},}$ ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}$

${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong \mathrm {C} _{2}\times \mathrm {C} _{2^{k-2}}.}$

Общие составные числа

По основной теореме о конечных абелевых группах группа изоморфна прямому произведению циклических групп простых степенных порядков. ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Более конкретно, китайская теорема об остатках ^[7] гласит, что если тогда кольцо является прямым произведением колец, соответствующих каждому из его простых степенных множителей: ${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}$

Аналогично, группа единиц является прямым произведением групп, соответствующих каждому из простых коэффициентов мощности: ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}$

Для каждой нечетной простой степени соответствующим фактором является циклическая группа порядка , которая может далее факторизоваться в циклические группы порядков простой степени. Для степеней 2 фактор не является циклическим, если только k = 0, 1, 2, а разлагается на циклические группы, как описано выше. ${\displaystyle p^{k}}$ ${\displaystyle (\mathbb {Z} /{p^{k}}\mathbb {Z} )^{\times }}$ ${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}}$ ${\displaystyle (\mathbb {Z} /{2^{k}}\mathbb {Z} )^{\times }}$

Порядок группы есть произведение порядков циклических групп в прямом произведении. Показатель группы, то есть наименьшее общее кратное порядков в циклических группах, задается функцией Кармайкла ( последовательность A002322 в OEIS ). Другими словами, это наименьшее число такое, что для каждого имеет место взаимно простое число с n . Оно делит и равно ему тогда и только тогда, когда группа циклическая. ${\displaystyle \varphi (n)}$ ${\displaystyle \lambda (n)}$ ${\displaystyle \lambda (n)}$ ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$ ${\displaystyle \varphi (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 элементов . ${\displaystyle \mathbb {Z} _{n}^{\times }}$ ${\displaystyle x^{n-1}=1}$ ${\displaystyle x\in \mathbb {Z} _{p}^{\times }}$ ${\displaystyle 2^{341-1}\equiv 1\mod 341}$ ${\displaystyle \mathbb {Z} _{341}^{\times }}$

Примеры

п = 9

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

п = 91

Для 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. ${\displaystyle \varphi (91)=72}$

п = 561

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

Примеры

В этой таблице показано циклическое разложение и порождающий набор для n ≤ 128. Разложение и порождающий набор не уникальны; например, ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

${\displaystyle \displaystyle {\begin{aligned}(\mathbb {Z} /35\mathbb {Z} )^{\times }&\cong (\mathbb {Z} /5\mathbb {Z} )^{\times }\times (\mathbb {Z} /7\mathbb {Z} )^{\times }\cong \mathrm {C} _{4}\times \mathrm {C} _{6}\cong \mathrm {C} _{4}\times \mathrm {C} _{2}\times \mathrm {C} _{3}\cong \mathrm {C} _{2}\times \mathrm {C} _{12}\cong (\mathbb {Z} /4\mathbb {Z} )^{\times }\times (\mathbb {Z} /13\mathbb {Z} )^{\times }\\&\cong (\mathbb {Z} /52\mathbb {Z} )^{\times }\end{aligned}}}$

(но ). В таблице ниже перечислено кратчайшее разложение (среди них выбирается первое лексикографически - это гарантирует, что изоморфные группы перечислены с одинаковыми разложениями). Генераторный набор также выбирается как можно более коротким, и для n с примитивным корнем указывается наименьший примитивный корень по модулю n . ${\displaystyle \not \cong \mathrm {C} _{24}\cong \mathrm {C} _{8}\times \mathrm {C} _{3}}$

Например, возьмите . Тогда означает, что порядок группы равен 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). ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$ ${\displaystyle \varphi (20)=8}$ ${\displaystyle \lambda (20)=4}$ ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$

Наименьший примитивный корень по модулю n равен (0, если корня не существует)

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (последовательность A046145 в OEIS )

Числа элементов минимального порождающего набора по модулю n равны

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (последовательность A046072 в OEIS )

Смотрите также

• Факторизация эллиптической кривой Ленстры

Примечания

1. Вайсштейн, Эрик В. «Группа умножения по модулю». Математический мир .
2. Первобытный корень, Энциклопедия математики
3. (Виноградов 2003, стр. 105–121, § VI ПРИМИТИВНЫЕ КОРНИ И ИНДЕКСЫ)
4. (Гаусс и Кларк, 1986, ст. 52–56, 82–891) harv error: no target: CITEREFGaussClarke1986 (help)
5. (Виноградов 2003, стр. 106)
6. (Гаусс и Кларк, 1986, ст. 90–91) harv error: no target: CITEREFGaussClarke1986 (help)
7. Обо всем этом рассказывает Ризель. (Ризель, 1994, стр. 267–275)
8. Эрдеш, Пол ; Померанс, Карл (1986). «О числе лжесвидетелей для составного числа». Математика вычислений . 46 (173): 259–279. дои : 10.1090/s0025-5718-1986-0815848-x . Збл  0586.10003.

Рекомендации

« Disquisitiones Arithmeticae» переведена с цицероновской латыни Гаусса на английский и немецкий языки . Немецкое издание включает все его статьи по теории чисел: все доказательства квадратичной взаимности , определение знака суммы Гаусса , исследования биквадратичной взаимности и неопубликованные заметки.

• Гаусс, Карл Фридрих (1986), Disquisitiones Arithmeticae (английский перевод, второе, исправленное издание) , перевод Кларка, Артура А., Нью-Йорк: Springer , ISBN 978-0-387-96254-2
• Гаусс, Карл Фридрих (1965), Untersuruchungen uber hohere Arithmetik (Disquisitiones Arithemetica & другие статьи по теории чисел) (немецкий перевод, второе издание) , перевод Мазера, Х., Нью-Йорк: Челси, ISBN 978-0-8284-0191-3
• Ризель, Ганс (1994), Простые числа и компьютерные методы факторизации (второе издание) , Бостон: Birkhäuser, ISBN 978-0-8176-3743-9
• Виноградов, И.М. (2003), «§ VI Примитивные корни и индексы», Элементы теории чисел , Минеола, Нью-Йорк: Dover Publications, стр. 105–121, ISBN 978-0-486-49530-9

Внешние ссылки

• Вайсштейн, Эрик В. «Группа умножения по модулю». Математический мир .
• Вайсштейн, Эрик В. «Примитивный корень». Математический мир .
• Веб-инструмент для интерактивного расчета групповых таблиц от Джона Джонса
• Последовательность OEIS A033948 (Числа, имеющие примитивный корень (мультипликативная группа по модулю n является циклической))
• Числа n такие, что мультипликативная группа по модулю n является прямым произведением k циклических групп:
  • k = 2 последовательности OEIS A272592 (2 циклические группы)
  • k = 3 последовательность OEIS A272593 (3 циклические группы)
  • k = 4 последовательности OEIS A272594 (4 циклические группы)
• Последовательность OEIS A272590 (наименьшее число m такое, что мультипликативная группа по модулю m является прямым произведением n циклических групп)