Примитивный корень по модулю п - Primitive root modulo n - Wikipedia

В модульная арифметика, филиал теория чисел, число грамм это примитивный корень по модулюп если каждый номер а совмещать к п является конгруэнтный к власти грамм по модулю п. То есть, грамм это примитивный корень по модулю п, если для каждого целого а взаимно простой с п, есть целое число k для которого грамм^k ≡ а (модп). Такое значение k называется индекс или же дискретный логарифм из а к базе грамм по модулю п. Обратите внимание, что грамм это примитивный корень по модулю п если и только если грамм является генератором мультипликативная группа целых чисел по модулю п.

Гаусс определены первобытные корни в Статья 57. из Disquisitiones Arithmeticae (1801 г.), где он указал Эйлер с введением термина. В Статья 56. он заявил, что Ламберт и Эйлер знал о них, но он был первым, кто строго продемонстрировал, что первобытные корни существуют для основной п. Фактически, Disquisitiones содержит два доказательства: одно в Статья 54. неконструктивный доказательство существования, а доказательство в Статья 55. является конструктивный.

Элементарный пример

Число 3 - это первообразный корень по модулю 7^[1] потому что

${\displaystyle {\begin{array}{rcrcrcrcrcr}3^{1}&=&3&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&9&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&27&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&81&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&243&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&729&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\3^{7}&=&2187&=&3^{6}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\\end{array}}}$

Здесь мы видим, что период из 3^k по модулю 7 равен 6. Остатки в периоде, которые равны 3, 2, 6, 4, 5, 1, образуют перестановку всех ненулевых остатков по модулю 7, подразумевая, что 3 действительно является примитивным корнем по модулю 7. Это происходит из факт, что последовательность (грамм^k по модулюп) всегда повторяется после некоторого значения k, поскольку по модулюп производит конечное количество значений. Если грамм примитивный корень по модулюп и п простое, то период повторения п − 1 . Любопытно, что созданные таким образом перестановки (и их круговые сдвиги) оказались Массивы Костаса.

Определение

Если п положительное целое число, целые числа от 0 до п − 1 которые совмещать к п (или, что то же самое, классы конгруэнтности взаимно простой с п) образуют группа, с умножением по модулю п как операция; это обозначается ℤ^×
_п, и называется группа единиц по модулю п, или группа примитивных классов по модулю п. Как объяснено в статье мультипликативная группа целых чисел по модулю п, эта мультипликативная группа (ℤ^×
_п) является циклический если и только если п равно 2, 4, п^k, или 2п^k куда п^k это сила странного простое число.^[2][3][4] Когда (и только когда) эта группа ℤ^×
_п циклический, а генератор этой циклической группы называется примитивный корень по модулю п^[5] (или более полным языком первообразный корень из единицы по модулю п, подчеркивая его роль как фундаментального решения корни единства полиномиальные уравнения X^м
- 1 в ринге ℤ_п) или просто примитивный элемент ℤ^×
_п. Когда ℤ^×
_п нециклический, такие примитивные элементы mod п не существует.

Для любого п (так или иначе ℤ^×
_п циклический), порядок (то есть количество элементов в) ℤ^×
_п дан кем-то Функция Эйлера φ(п) (последовательность A000010 в OEIS ). А потом, Теорема Эйлера Говорит, что а^φ(п) ≡ 1 (мод п) для каждого а взаимно простой с п; самая низкая мощность а что сравнимо с 1 по модулю п называется мультипликативный порядок из а по модулю п. В частности, для а быть примитивным корнем по модулю п, φ(п) должно быть наименьшей степенью а что сравнимо с 1 по модулю п.

Примеры

Например, если п = 14 затем элементы ℤ^×
_п - классы конгруэнции {1, 3, 5, 9, 11, 13}; Существуют φ(14) = 6 их. Вот таблица их мощностей по модулю 14:

 х х, х2, Икс3, ... (мод. 14) 1: 1 3: 3, 9, 13, 11, 5, 1 5: 5, 11, 13, 9, 3, 1 9: 9, 11, 111: 11, 9, 113 : 13, 1

Порядок 1 равен 1, порядки 3 и 5 равны 6, порядки 9 и 11 равны 3, а порядок 13 равен 2. Таким образом, 3 и 5 являются первообразными корнями по модулю 14.

Для второго примера пусть п = 15 . Элементы ℤ^×
₁₅ - классы конгруэнции {1, 2, 4, 7, 8, 11, 13, 14}; Существуют φ(15) = 8 их.

 х х, х2, Икс3, ... (мод. 15) 1: 1 2: 2, 4, 8, 1 4: 4, 1 7: 7, 4, 13, 1 8: 8, 4, 2, 111: 11, 113: 13, 4, 7, 114: 14, 1

Поскольку не существует числа с порядком 8, не существует примитивных корней по модулю 15. В самом деле, λ(15) = 4, куда λ это Функция Кармайкла. (последовательность A002322 в OEIS )

Таблица первобытных корней

Числа с примитивным корнем:

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149, ... (последовательность A033948 в OEIS )

Это таблица первобытных корней Гаусса из Disquisitiones. В отличие от большинства современных авторов он не всегда выбирал наименьший первобытный корень. Вместо этого он выбрал 10, если это примитивный корень; если это не так, он выбрал тот корень, который дает 10 наименьший индекс, и, если их больше одного, выбрал наименьший из них. Это не только упрощает ручные вычисления, но и используется в § VI, где исследуются периодические десятичные разложения рациональных чисел.

Строки таблицы помечены значком основные силы (кроме 2, 4 и 8) менее 100; второй столбец - это примитивный корень по модулю этого числа. Столбцы помечены простым числом меньше 100. Запись в строке п, столбец q это индекс q по модулю п для данного корня.

Например, в строке 11 значение 2 дано как первообразный корень, а в столбце 5 запись равна 4. Это означает, что 2⁴ = 16 ≡ 5 (мод 11).

Для индекса составного числа сложите индексы его простых множителей.

Например, в строке 11 индекс 6 представляет собой сумму индексов для 2 и 3: 2^{1 + 8} = 512 ≡ 6 (мод 11). Индекс 25 вдвое больше индекса 5: 2⁸ = 256 ≡ 25 (мод 11). (Конечно, поскольку 25 ≡ 3 (мод 11), запись для 3 - 8).

Таблица для нечетных простых степеней проста. Но степени 2 (16, 32 и 64) не имеют примитивных корней; вместо этого, степени 5 составляют половину нечетных чисел, меньших степени 2, а их отрицательные значения по модулю степени 2 составляют вторую половину. Все степени 5 равны 5 или 1 (по модулю 8); столбцы, озаглавленные числами, равными 3 или 7 (mod 8), содержат индекс его отрицательного значения. (Последовательность A185189 и A185268 в OEIS )

Например, по модулю 32 индекс для 7 равен 2, а 5² = 25 ≡ −7 (mod 32), но запись для 17 равна 4, и 5⁴ = 625 ≡ 17 (мод 32).

Первобытные корни и индексы
(остальные столбцы - это индексы целых чисел под заголовками соответствующих столбцов)

п	корень	2	3	5	7	11		13	17	19	23	29		31	37	41	43	47		53	59	61	67	71		73	79	83	89	97
3	2	1
5	2	1	3
7	3	2	1	5
9	2	1	*	5	4
11	2	1	8	4	7
13	6	5	8	9	7	11
16	5	*	3	1	2	1		3
17	10	10	11	7	9	13		12
19	10	17	5	2	12	6		13	8
23	10	8	20	15	21	3		12	17	5
25	2	1	7	*	5	16		19	13	18	11
27	2	1	*	5	16	13		8	15	12	11
29	10	11	27	18	20	23		2	7	15	24
31	17	12	13	20	4	29		23	1	22	21	27
32	5	*	3	1	2	5		7	4	7	6	3		0
37	5	11	34	1	28	6		13	5	25	21	15		27
41	6	26	15	22	39	3		31	33	9	36	7		28	32
43	28	39	17	5	7	6		40	16	29	20	25		32	35	18
47	10	30	18	17	38	27		3	42	29	39	43		5	24	25	37
49	10	2	13	41	*	16		9	31	35	32	24		7	38	27	36	23
53	26	25	9	31	38	46		28	42	41	39	6		45	22	33	30	8
59	10	25	32	34	44	45		28	14	22	27	4		7	41	2	13	53		28
61	10	47	42	14	23	45		20	49	22	39	25		13	33	18	41	40		51	17
64	5	*	3	1	10	5		15	12	7	14	11		8	9	14	13	12		5	1	3
67	12	29	9	39	7	61		23	8	26	20	22		43	44	19	63	64		3	54	5
71	62	58	18	14	33	43		27	7	38	5	4		13	30	55	44	17		59	29	37	11
73	5	8	6	1	33	55		59	21	62	46	35		11	64	4	51	31		53	5	58	50	44
79	29	50	71	34	19	70		74	9	10	52	1		76	23	21	47	55		7	17	75	54	33		4
81	11	25	*	35	22	1		38	15	12	5	7		14	24	29	10	13		45	53	4	20	33		48	52
83	50	3	52	81	24	72		67	4	59	16	36		32	60	38	49	69		13	20	34	53	17		43	47
89	30	72	87	18	7	4		65	82	53	31	29		57	77	67	59	34		10	45	19	32	26		68	46	27
97	10	86	2	11	53	82		83	19	27	79	47		26	41	71	44	60		14	65	32	51	25		20	42	91	18
п	корень	2	3	5	7	11		13	17	19	23	29		31	37	41	43	47		53	59	61	67	71		73	79	83	89	97

В следующей таблице перечислены примитивные корни по модулю п за п ≤ 72:

${\displaystyle n}$	примитивные корни по модулю ${\displaystyle n}$	порядок (OEIS: A000010)	${\displaystyle n}$	примитивные корни по модулю ${\displaystyle n}$	порядок (OEIS: A000010)
1	0	1	37	2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35	36
2	1	1	38	3, 13, 15, 21, 29, 33	18
3	2	2	39		24
4	3	2	40		16
5	2, 3	4	41	6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35	40
6	5	2	42		12
7	3, 5	6	43	3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34	42
8		4	44		20
9	2, 5	6	45		24
10	3, 7	4	46	5, 7, 11, 15, 17, 19, 21, 33, 37, 43	22
11	2, 6, 7, 8	10	47	5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45	46
12		4	48		16
13	2, 6, 7, 11	12	49	3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 47	42
14	3, 5	6	50	3, 13, 17, 23, 27, 33, 37, 47	20
15		8	51		32
16		8	52		24
17	3, 5, 6, 7, 10, 11, 12, 14	16	53	2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51	52
18	5, 11	6	54	5, 11, 23, 29, 41, 47	18
19	2, 3, 10, 13, 14, 15	18	55		40
20		8	56		24
21		12	57		36
22	7, 13, 17, 19	10	58	3, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 55	28
23	5, 7, 10, 11, 14, 15, 17, 19, 20, 21	22	59	2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56	58
24		8	60		16
25	2, 3, 8, 12, 13, 17, 22, 23	20	61	2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59	60
26	7, 11, 15, 19	12	62	3, 11, 13, 17, 21, 43, 53, 55	30
27	2, 5, 11, 14, 20, 23	18	63		36
28		12	64		32
29	2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27	28	65		48
30		8	66		20
31	3, 11, 12, 13, 17, 21, 22, 24	30	67	2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63	66
32		16	68		32
33		20	69		44
34	3, 5, 7, 11, 23, 27, 29, 31	16	70		24
35		24	71	7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69	70
36		12	72		24

Гипотеза Артина о первобытных корнях заявляет, что данное целое число а это ни идеальный квадрат ни −1 не является первообразным корнем по модулю бесконечного числа простые числа.

Последовательность наименьших первообразных корней по модулю п (что не то же самое, что последовательность примитивных корней в таблице Гаусса)

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, ... (последовательность A046145 в OEIS )

Для премьер п, они есть

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, ... (последовательность A001918 в OEIS )

Наибольшие первообразные корни по модулю п находятся

0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, ... (последовательность A046146 в OEIS )

Для премьер п, они есть

1, 2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45, 51, 56, 59, 63, 69, 68, 77, 80, 86, 92, 99, 101, 104, 103, 110, 118, 128, 134, 135, 147, 146, 152, 159, 165, 171, 176, 179, 189, 188, 195, 197, 207, 214, 224, 223, ... (последовательность A071894 в OEIS )

Количество первообразных корней по модулю п находятся

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, ... (последовательность A046144 в OEIS )

Для премьер п, они есть

1, 1, 2, 2, 4, 4, 8, 6, 10, 12, 8, 12, 16, 12, 22, 24, 28, 16, 20, 24, 24, 24, 40, 40, 32, 40, 32, 52, 36, 48, 36, 48, 64, 44, 72, 40, 48, 54, 82, 84, 88, 48, 72, 64, 84, 60, 48, 72, 112, 72, 112, 96, 64, 100, 128, 130, 132, 72, 88, 96, ... (последовательность A008330 в OEIS )

Наименьшее простое число> п с первобытным корнем п находятся

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53, ... (последовательность A023049 в OEIS )

Наименьшее простое число (не обязательно превышающее п) с первообразным корнем п находятся

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, ... (последовательность A056619 в OEIS )

Арифметические факты

Гаусс доказал^[6] что для любого простого числа п (за исключением п = 3 ), произведение его примитивных корней сравнимо с 1 по модулю п.

Он также доказал^[7] что для любого простого числа п, сумма его примитивных корней конгруэнтна μ(п - 1) по модулю п, куда μ это Функция Мёбиуса.

Например,

п = 3, μ(2) = -1. Первоначальный корень равен 2.

п = 5, μ(4) = 0. Первоначальные корни - 2 и 3.

п = 7, μ(6) = 1. Первоначальные корни равны 3 и 5.

п = 31, μ(30) = −1. Первоначальные корни - это 3, 11, 12, 13, 17, 21, 22 и 24.

Их произведение 970377408 1 (mod 31) и их сумма 123 ≡ −1 (mod 31).

3 × 11 = 33 ≡ 2

12 × 13 = 156 ≡ 1

(−14) × (−10) = 140 ≡ 16

(−9) × (−7) = 63 1 и 2 × 1 × 16 × 1 = 32 1 (mod 31).

А как насчет сложения элементов этой мультипликативной группы? Как это бывает, суммы (или разности) двух примитивных корней складываются во все элементы подгруппы индекса 2 ℤ/п ℤ даже для п, и всей группе ℤ/п ℤ когда п странно:

 ℤ/п ℤ× + ℤ/п ℤ× = ℤ/п ℤ или 2ℤ/п ℤ .[8]

Поиск первобытных корней

Нет простой общей формулы для вычисления первообразных корней по модулю п известен.^[а][b] Однако есть методы для поиска первообразного корня, которые быстрее, чем просто пробовать всех кандидатов. Если мультипликативный порядок из числа м по модулю п равно ${\displaystyle \varphi (n)}$ (получатель чего-то ℤ^×
_п), то это примитивный корень. На самом деле верно и обратное: если м примитивный корень по модулю п, то мультипликативный порядок м является ${\displaystyle \varphi (n)}$. Мы можем использовать это для проверки кандидата м чтобы увидеть, примитивен ли он.

Сначала вычислим ${\displaystyle \varphi (n)}$. Затем определите разные главные факторы из ${\displaystyle \varphi (n)}$, сказать п₁, ..., п_k. Наконец, вычислим

${\displaystyle m^{\varphi (n)/p_{i}}{\bmod {n}}\qquad {\mbox{ for }}i=1,\ldots ,k}$

используя быстрый алгоритм для модульное возведение в степень Такие как возведение в степень возведением в квадрат. Число м для чего эти k результаты все отличаются от 1 - это примитивный корень.

Количество первообразных корней по модулю п, если есть, равно^[9]

${\displaystyle \varphi \left(\varphi (n)\right)}$

поскольку, вообще говоря, циклическая группа с р элементы имеют ${\displaystyle \varphi (r)}$ генераторы. Для премьер п, это равно ${\displaystyle \varphi (n-1)}$, и с тех пор ${\displaystyle n/\varphi (n-1)\in O(\log \log n)}$ генераторы очень распространены среди {2, ..., п−1}, поэтому найти его относительно легко.^[10]

Если грамм примитивный корень по модулю п, тогда грамм также является примитивным корнем по модулю всех степеней п^k пока не грамм^п−1 ≡ 1 (мод п²); в таком случае, грамм + п является.^[11]

Если грамм примитивный корень по модулю п^k, то либо грамм или же грамм + п^k (какой из них нечетный) является первообразным корнем по модулю 2п^k.^[11]

Нахождение первообразных корней по модулю п также эквивалентно нахождению корней (п - 1) ул. круговой полином по модулю п.

Порядок первобытных корней

Наименее примитивный корень грамм_п по модулю п (в диапазоне 1, 2, ..., п − 1 ) вообще маленький.

Верхняя граница

Берджесс (1962) доказал^[12] это для каждого ε > 0 есть C такой, что ${\displaystyle g_{p}\leq C\,p^{{\frac {1}{4}}+\epsilon }~.}$

Гроссвальд (1981) доказал^[12] что если ${\displaystyle p>e^{e^{24}}}$, тогда ${\displaystyle g_{p}<p^{0.499}~.}$

Карелла (2015) доказала^[13] что есть ${\displaystyle C>0}$ такой, что ${\displaystyle g_{p}\leq C\,p^{5/\log \log p}}$ для всех достаточно больших простых чисел ${\displaystyle p>2~.}$

Shoup (1990, 1992) доказали,^[14] предполагая обобщенная гипотеза Римана, который грамм_п = O (журнал⁶ п).

Нижние оценки

Фридландер (1949) и Салье (1950) доказали, что^[12] что есть положительная константа C такой, что для бесконечно большого числа простых чисел грамм_п > C бревно п .

Это можно доказать^[12] элементарным образом, что для любого положительного целого числа M существует бесконечно много таких простых чисел, что M < грамм_п < п − M .

Приложения

Примитивный корень по модулю п часто используется в криптография, в том числе Обмен ключами Диффи – Хеллмана схема. Звуковые диффузоры были основаны на теоретико-числовых концепциях, таких как первообразные корни и квадратичные вычеты.^[15][16]

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

• Гипотеза Артина о первобытных корнях
• Dirichlet персонаж
• Полный репенд прайм
• Обобщение Гаусса теоремы Вильсона
• Мультипликативный порядок
• Квадратичный остаток
• Корень единства по модулю п

Сноски

1. «Одна из важнейших нерешенных проблем теории конечных полей - это разработка быстрого алгоритма построения первообразных корней. фон цур Гатен и Шпарлински 1998, стр. 15–24
2. «Не существует удобной формулы для вычисления [наименьшего примитивного корня]». Роббинс 2006, п. 159

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

1. Стромквист, Уолтер. "Что такое первобытные корни?". Математика. Колледж Брин-Мор. Архивировано из оригинал на 2017-07-03. Получено 2017-07-03.
2. Вайсштейн, Эрик В. "Группа умножения по модулю". MathWorld.
3. Первобытный корень, Энциклопедия математики.
4. Виноградов 2003, pp. 105–121, § VI Первобытные корни и индексы.
5. Виноградов 2003, п. 106.
6. Гаусс и Кларк 1986, искусства. 80 Ошибка harvnb: цель отсутствует: CITEREFGaussClarke1986 (помощь).
7. Гаусс и Кларк 1986, арт 81 Ошибка harvnb: цель отсутствует: CITEREFGaussClarke1986 (помощь).
8. Амиот, Эммануэль (2016). Музыка через пространство Фурье. Серия CMS. Цюрих, Швейцария: Springer. п. 38. ISBN  978-3-319-45581-5.
9. (последовательность A010554 в OEIS )
10. Кнут, Дональд Э. (1998). Получисловые алгоритмы. Искусство программирования. 2 (3-е изд.). Аддисон-Уэсли. раздел 4.5.4, с. 391.
11. Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел. Берлин: Springer. п. 26. ISBN  978-3-540-55640-4.
12. Рибенбойм, Пауло (1996). Новая книга рекордов простых чисел. Нью-Йорк, штат Нью-Йорк: Springer. п. 24. ISBN  978-0-387-94457-9.
13. Карелла, Н.А. (2015). «Наименьшие первичные примитивные корни». Международный журнал математики и информатики. 10 (2): 185–194. arXiv:1709.01172.
14. Бах и Шаллит 1996, п. 254.
15. Уокер, Р. (1990). Конструкция и применение модульных акустических рассеивающих элементов. (PDF). Исследовательский отдел BBC (Отчет). Британская радиовещательная корпорация. Получено 25 марта 2019.
16. Фельдман, Элиот (июль 1995 г.). «Отражательная решетка, которая устраняет зеркальное отражение: конус тишины». J. Acoust. Soc. Являюсь. 98 (1): 623–634. Bibcode:1995ASAJ ... 98..623F. Дои:10.1121/1.413656.

Источники

• Бах, Эрик; Шаллит, Джеффри (1996). Эффективные алгоритмы. Алгоритмическая теория чисел. я. Кембридж, Массачусетс: MIT Press. ISBN  978-0-262-02405-1.

• Карелла, Н. А. (2015). «Наименьшие первичные примитивные корни». Международный журнал математики и информатики. 10 (2): 185–194. arXiv:1709.01172.

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

• Гаусс, Карл Фридрих (1986) [1801]. Disquisitiones Arithmeticae. Перевод Кларка, Артур А. (2-е, исправленное изд.). Нью-Йорк, штат Нью-Йорк: Springer. ISBN  978-0-387-96254-2.

• Гаусс, Карл Фридрих (1965) [1801]. Untersuchungen über höhere Arithmetik [Исследования высшей арифметики] (на немецком). Перевод Maser, H. (2-е изд.). Нью-Йорк, Нью-Йорк: Челси. ISBN  978-0-8284-0191-3.

• Роббинс, Невилл (2006). Начальная теория чисел. Джонс и Бартлетт Обучение. ISBN  978-0-7637-3768-9.

• Виноградов, И. (2003). "§ VI Первобытные корни и индексы". Элементы теории чисел. Минеола, Нью-Йорк: Dover Publications. С. 105–121. ISBN  978-0-486-49530-9.

• фон цур Гатен, Иоахим; Шпарлинский, Игорь (1998). «Порядки периодов Гаусса в конечных полях». Применимая алгебра в инженерии, коммуникации и вычислениях. 9 (1): 15–24. CiteSeerX  10.1.1.46.5504. Дои:10.1007 / s002000050093. МИСТЕР  1624824. S2CID  19232025.

дальнейшее чтение

• Оре, Ойштейн (1988). Теория чисел и ее история. Дувр. стр.284–302. ISBN  978-0-486-65620-5..

внешняя ссылка

• Вайсштейн, Эрик В. «Первобытный корень». MathWorld.
• Холт. «Квадратичные вычеты и первообразные корни». Математика. Michigan Tech.
• "Калькулятор первобытных корней". BlueTulip.