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

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

Алгебраическая структура → Теория групп Теория групп
Основные понятия Подгруппа Нормальная подгруппа Факторная группа (Полу) прямой продукт Групповые гомоморфизмы ядро изображение прямая сумма венок просто конечный бесконечный непрерывный мультипликативный добавка циклический абелевский двугранный нильпотентный разрешимый Глоссарий теории групп Список тем теории групп
Конечные группы Классификация конечных простых групп циклический чередование Тип лжи спорадический Теорема Коши Теорема Лагранжа Теоремы Силова Теорема холла p-группа Элементарная абелева группа Группа Фробениуса Множитель Шура Симметричная группа S n Клейн четыре группы V Группа диэдра D n Группа кватернионов Q Дициклическая группа Dic n
Дискретные группы Решетки Целые числа ( Z ) Бесплатная группа Модульные группы PSL (2; Z ) SL (2, Z ) Арифметическая группа Решетка Гиперболическая группа
Топологические группы и группы Ли Соленоид Круг Общая линейная GL ( n ) Специальная линейная SL ( n ) Ортогональный O ( n ) Евклидова E ( n ) Специальный ортогональный SO ( n ) Унитарный U ( n ) Специальная унитарная СУ ( п ) Симплектический Sp ( n ) G 2 П 4 E 6 E 7 E 8 Лоренц Пуанкаре Конформный Диффеоморфизм Петля Бесконечномерная группа Ли O (∞) SU (∞) Sp (∞)
Алгебраические группы Линейная алгебраическая группа Редуктивная группа Абелева разновидность Эллиптическая кривая
v т е

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

Наконец, с учетом более , то мультипликативный обратный из более по модулю п представляет собой целое число х , удовлетворяющее ах ≡ 1 ( по модулю п ) . Он существует именно тогда, когда a взаимно просто с n , потому что в этом случае gcd ( a , n ) = 1 и по лемме Безу существуют целые числа x и y, удовлетворяющие ax + ny = 1 . Обратите внимание, что из уравнения ax + ny = 1 следует, чтоx взаимно прост с n , поэтому мультипликативный обратный принадлежит группе.

Обозначение [ править ]

Множество (классов сравнения) целых чисел по модулю n с операциями сложения и умножения представляет собой кольцо . Он обозначается   или    (обозначение относится к делению целых чисел по модулю идеала или состоящих из кратных n ). Вне теории чисел часто используются более простые обозначения , хотя их можно спутать с p -адическими целыми числами, когда n - простое число.${\ Displaystyle \ mathbb {Z} / п \ mathbb {Z}}$${\ Displaystyle \ mathbb {Z} / (п)}$ ${\ Displaystyle п \ mathbb {Z}}$${\ Displaystyle (п)}$${\ Displaystyle \ mathbb {Z} _ {п}}$

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

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

Структура [ править ]

Порядок мультипликативной группы целых чисел по модулю n - это количество целых чисел, взаимно простых с n . Он задается функцией totient Эйлера : (последовательность A000010 в OEIS ). Для простого р , .${\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))}$

Степень двойки [ править ]

По модулю 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 \;.}$

Для каждой нечетной степени простого числа соответствующий множитель представляет собой циклическую группу порядка , которая может дополнительно разлагаться на циклические группы порядков степени простого числа. Для степеней двойки множитель не является циклическим, если 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 }}$

Порядок группы - это произведение порядков циклических групп в прямом произведении. Показатель в группе, то есть наименьшее общее кратное порядков в циклических групп, задается функцией Carmichael (последовательность A002322 в OEIS ). Другими словами, это наименьшее число такое , что для каждого в копервичных к п , имеет место. Он делится и равен ему тогда и только тогда, когда группа циклическая.${\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 . (Поскольку вычет 1 при возведении в любую степень сравним с 1 по модулю n , множество таких элементов непусто.) ^[8] Можно сказать, из-за Маленькой теоремы Ферма , что такие вычеты являются «ложноположительными» или «ложными». свидетелей »за первобытность п . Число 2 - это остаток, наиболее часто используемый в этой базовой проверке на простоту, поэтому 341 = 11 × 31 известен с тех пор, как ²³⁴⁰сравнимо с 1 по модулю 341, а 341 - наименьшее такое составное число (относительно 2). Для 341 подгруппа ложных свидетелей содержит 100 остатков и, следовательно, имеет индекс 3 внутри мультипликативной группы из 300 элементов по модулю 341.

Примеры [ править ]

n = 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 .

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, так как при этих значениях х , х ⁹⁰ сравнимо с 1 по модулю 91.${\displaystyle \varphi (91)=72}$

n = 561 [ править ]

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

Примеры [ править ]

В этой таблице показано циклическое разложение и порождающий набор для n ≤ 128. Разбиение и порождающие множества не уникальны; например (но ). В таблице ниже перечислены кратчайшие декомпозиции (среди них выбирается лексикографически первое - это гарантирует, что изоморфные группы будут перечислены с одинаковыми разложениями). Генератор также выбирается как можно короче, а для n с первообразным корнем указывается наименьший примитивный корень по модулю n .${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$${\displaystyle (\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}}$${\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 равны

0, 0, 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 )

Групповая структура (Z / n Z) ^×

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

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

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. "Группа умножения по модулю" . MathWorld .
• Вайсштейн, Эрик В. «Первобытный корень» . MathWorld .
• Веб-инструмент для интерактивного вычисления групповых таблиц от Джона Джонса