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

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

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

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

Наконец, при заданном a , мультипликативное обратное число 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, p ^k или 2 p ^k , где 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 ⁹⁰ сравнимо с 1 mod 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 (mod 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 )

Числа элементов в минимальном порождающем наборе mod 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. "Первобытный корень - Энциклопедия математики". encyclopediaofmath.org . Получено 2024-07-06 .
3. Виноградов 2003, стр. 105–121, § VI ПЕРВООБРАЗНЫЕ КОРНИ И ИНДЕКСЫ
4. Гаусс 1986, статьи 52–56, 82–891.
5. Виноградов 2003, стр. 106.
6. Гаусс 1986, статьи 90–91.
7. Ризель охватывает все это. Ризель 1994, стр. 267–275.
8. Эрдёш, Пол ; Померанс, Карл (1986). «О числе ложных свидетелей для составного числа». Математика вычислений . 46 (173): 259–279. doi : 10.1090/s0025-5718-1986-0815848-x . Zbl  0586.10003.

Ссылки

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

• Гаусс, Карл Фридрих (1986), Disquisitiones Arithmeticae (английский перевод, второе, исправленное издание) , перевод Кларка, Артура А., Нью-Йорк: Springer , ISBN 978-0-387-96254-2
• Гаусс, Карл Фридрих (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae и другие работы по теории чисел) (перевод на немецкий язык, второе издание) , перевод Мазера, Х., Нью-Йорк: Челси, 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

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

• Вайсштейн, Эрик В. «Группа умножения по модулю». Математический мир .
• Вайсштейн, Эрик В. «Первобытный корень». MathWorld .
• Веб-инструмент для интерактивного вычисления групповых таблиц Джона Джонса
• Последовательность 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 циклических групп)