Raiz primitiva módulo n

Na aritmética modular, um ramo da teoria dos números, um número $g$ é uma raiz primitiva módulo n se todo número $a$ coprimo a $n$ for congruente com uma potência de $g$ módulo $n$. Ou seja, $g$ é uma raiz primitiva módulo $n$ se para cada inteiro $a$ coprimo com $n$, existe um inteiro $k$ tal que $g^{k}\equiv a\ (\mathrm {mod} \ n)$. Esse valor $k$ é chamado de índice ou logaritmo discreto de $a$ para a base $g$ módulo $n$. Observe que $g$ é uma raiz primitiva do módulo $n$ se e somente se $g$ é um gerador do grupo multiplicativo de inteiros módulo n.

Gauss definiu raízes primitivas no Artigo 57 do Disquisitiones Arithmeticae (1801), onde ele atribuiu a Euler a cunhagem do termo. No Artigo 56, ele afirmou que Lambert e Euler sabiam deles, mas ele foi o primeiro a demonstrar rigorosamente que raízes primitivas existem para um $n$ primo. Na verdade, o Disquisitiones contém duas provas: a do Artigo 54 é uma prova de existência não construtiva, enquanto a outra do Artigo 55 é construtiva.

Exemplo elementar

O número 3 é uma raiz primitiva módulo 7 porque

${\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}}$

Aqui, vemos que o período de 3^k módulo 7 é 6. Os restantes no período, que são 3, 2, 6, 4, 5, 1, formam um rearranjo de todos os resíduos diferentes de zero módulo 7, implicando que 3 é de fato uma raiz primitiva módulo 7. Isso deriva do fato de que uma sequência ($g^{k}$ módulo $n$) sempre se repete após algum valor de $k$, uma vez que o módulo $n$ produz um número finito de valores. Se $g$ for uma raiz primitiva módulo $n$ e $n$ for primo, o período de repetição será $n-1$. Curiosamente, as permutações criadas dessa maneira (e seus deslocamentos circulares) mostraram ser matrizes de Costas.

Definição

Se $n$ for um inteiro positivo, os inteiros entre $0$ e $n-1$ que são coprimos com $n$ (ou equivalentemente, as classes de congruência coprimos com $n$) formam um grupo, com multiplicação módulo $n$ como operação; é denotado por $\mathbf {Z} _{n}^{x}$, e é chamado de grupo de unidades módulo $n$, ou grupo de classes primitivas módulo $n$. Conforme explicado no artigo grupo multiplicativo de inteiros módulo n, este grupo multiplicativo ($\mathrm {Z} _{n}^{x}$) é cíclico se e somente se $n$ for igual a $2$, $4$, $p^{k}$ ou $2p^{k}$, onde $p^{k}$ é uma potência de um número primo ímpar. Quando (e somente quando) este grupo $\mathrm {Z} _{n}^{x}$ é cíclico, um gerador deste grupo cíclico é chamado de raiz primitiva módulo n (ou em linguagem mais completa raiz primitiva de unidade módulo n, enfatizando seu papel como uma solução fundamental das raízes de unidade das equações polinomiais $X^{m}-1$ no anel $\mathbf {Z} _{n}$), ou simplesmente um elemento primitivo de $\mathbf {Z} _{n}^{x}$. Quando $\mathrm {Z} _{n}^{x}$ é não-cíclico, tais elementos primitivos mod $n$ não existem.

Para qualquer $n$ (seja ou não $\mathrm {Z} _{n}^{x}$ cíclico), a ordem de (ou seja, o número de elementos em) $\mathbf {Z} _{n}^{x}$ é dada pela função totiente de Euler $\varphi (n)$ (sequência A000010 na OEIS). E então, o teorema de Euler diz que $a^{\varphi (n)}\equiv 1\ (\mathrm {mod} \ n)$ para todo $a$ coprimo com $n$; a menor potência de $a$ que é congruente a $1{\bmod {n}}$ é chamada de ordem multiplicativa de $a$ módulo $n$. Em particular, para $a$ ser uma raiz primitiva módulo $n$, $\varphi (n)$ tem que ser a menor potência de $a$ que é congruente a $1{\bmod {n}}$.

Exemplos

Por exemplo, se $n=14$, então os elementos de $\mathbf {Z} _{14}^{x}$ são as classes de congruência $\{1,3,5,9,11,13\}$; existem $\varphi (14)=6$ deles. Aqui está uma tabela de suas potências módulo 14:

 x     x, x2, x3, ... (mod 14)
 1 :   1
 3 :   3,  9, 13, 11,  5,  1
 5 :   5, 11, 13,  9,  3,  1
 9 :   9, 11,  1
11 :  11,  9,  1
13 :  13,  1

A ordem de 1 é 1, as ordens de 3 e 5 são 6, as ordens de 9 e 11 são 3 e a ordem de 13 é 2. Assim, 3 e 5 são as raízes primitivas módulo 14.

Para um segundo exemplo, seja $n=15$. Os elementos de $\mathbf {Z} _{15}^{x}$ são as classes de congruência $\{1,2,4,7,8,11,13,14\}$; existem $\varphi (15)=8$ deles.

 x     x, x2, x3, ... (mod 15)
 1 :   1
 2 :   2,  4,  8, 1
 4 :   4,  1
 7 :   7,  4, 13, 1
 8 :   8,  4,  2, 1
11 :  11,  1
13 :  13,  4,  7, 1
14 :  14,  1

Como não há número cuja ordem seja 8, não há raízes primitivas módulo 15. De fato, $\lambda (15)=4$, onde $\lambda$ é a função de Carmichael. (sequência A002322 na OEIS)

Tabela de raízes primitivas

Números que têm uma raiz primitiva são

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, ... (sequência A033948 na OEIS)

Esta é a tabela de Gauss das raízes primitivas de Disquisitiones. Ao contrário da maioria dos autores modernos, ele nem sempre escolhia a menor raiz primitiva. Em vez disso, ele escolhia 10 se for uma raiz primitiva; se não for, ele escolhia a raiz que dá 10 o menor índice e, se houver mais de uma, escolhe a menor delas. Isso não é apenas para tornar o cálculo manual mais fácil, mas é usado no § VI, onde as expansões decimais periódicas de números racionais são investigadas.

As linhas da tabela são rotuladas com as potências primas (exceto 2, 4 e 8) menor que 100; a segunda coluna é um módulo raiz primitivoa desse número. As colunas são rotuladas com os primos menores que 100. A entrada na linha p, coluna q é o índice de q módulo p para a raiz fornecida.

Por exemplo, na linha $11$, $2$ é dado como a raiz primitiva e na coluna $5$ a entrada é $4$. Isso significa que $2^{4}=16\equiv 5\ (\mathrm {mod} \ 11)$.

Para o índice de um número composto, some os índices de seus fatores primos.

Por exemplo, na linha $11$, o índice de $6$ é a soma dos índices para $2$ e $3$: $2^{1+8}=512\equiv 6\ (\mathrm {mod} \ 11)$. O índice de $25$ é o dobro do índice $5$: $2^{8}=256\equiv 25\ (\mathrm {mod} \ 11)$. (Claro, como $25\equiv 3\ (\mathrm {mod} \ 11)$, a entrada para $3$ é $8$).

A tabela é simples para as potências primas ímpares. Mas as potências de 2 (16, 32 e 64) não têm raízes primitivas; em vez disso, as potências de 5 respondem por metade dos números ímpares menores que a potência de 2, e seus módulos negativos, as potências de 2 respondem pela outra metade. Todas as potências de 5 são $\equiv 5$ ou $1\ (\mathrm {mod} \ 8)$; as colunas encabeçadas por números $\equiv 3$ ou $7\ (\mathrm {mod} \ 8)$ contêm o índice de seu negativo. (sequência A185189 na OEIS) e (sequência A185268 na OEIS)

Por exemplo, no módulo $32$ o índice para $7$ é $2$ e $5^{2}=25\equiv -7\ (\mathrm {mod} \ 32)$, mas a entrada para $17$ é $4$ e $5^{4}=625\equiv 17\ (\mathrm {mod} \ 32)$.

Raízes primitivas e índices
(outras colunas são os índices de inteiros sob os respectivos títulos das colunas)

n	raiz	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
n	raiz	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

A tabela a seguir lista as raízes primitivas módulo $n$ para $n\leq 72$:

$n$	raízes primitivas módulo $n$	ordem (OEIS: A000010)	$n$	raízes primitivas módulo $n$	ordem (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

A conjectura de Artin sobre as raízes primitivas afirma que um dado inteiro $a$ que não é um quadrado perfeito nem $-1$ é uma raiz primitiva módulo infinitos primos.

A sequência de menores raízes primitivas módulo $n$ (que não é a mesma que a sequência de raízes primitivas na tabela de Gauss) são

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, ... (sequência A046145 na OEIS)

Para $n$ primo, elas são

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, ... (sequência A001918 na OEIS)

As maiores raízes primitivas módulo $n$ são

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, ... (sequência A046146 na OEIS)

Para $n$ primo, elas são

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, ... (sequência A071894 na OEIS)

Número de raízes primitivas módulo $n$ são

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, ... (sequência A046144 na OEIS)

Para $n$ primo, elas são

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, ... (sequência A008330 na OEIS)

Menor primo $>n$ com raiz primitiva $n$ são

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, ... (sequência A023049 na OEIS)

Menor primo (não necessariamente excedendo $n$) com raiz primitiva $n$ são

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, ... (sequência A056619 na OEIS)

Fatos aritméticos

Gauss provou que para qualquer número primo $p$ (com a única exceção de $p=3$), o produto de suas raízes primitivas é congruente a $1$ módulo $p$.

Ele também provou que para qualquer número primo $p$, a soma de suas raízes primitivas é congruente com $\mu (p-1)$ módulo $p$, onde $\mu$ é a função de Möbius.

Por exemplo,

$p=3$, $\mu (2)=-1$. A raiz primitiva é $2$.

$p=5$, $\mu (4)=0$. The primitive roots are $2$ and $3$.

$p=7$, $\mu (6)=1$. The primitive roots are $3$ and $5$.

$p=31$, $\mu (30)=-1$. The primitive roots are $3$, $11$, $12$, $13$, $17$, $21$, $22$ e $24$.

Seu produto $970377408\equiv 1\ (\mathrm {mod} \ 31)$ e sua soma $123\equiv -1\ (\mathrm {mod} \ 31)$.

$3\times 11=33\equiv 2$

$12\times 13=156\equiv 1$

$(-14)\times (-10)=140\equiv 16$

$(-9)\times (-7)=63\equiv 1,\quad {\text{e}}\quad 2\times 1\times 16\times 1=32\equiv 1\ (\mathrm {mod} \ 31)$.

As somas (ou diferenças) de duas raízes primitivas somam todos os elementos do subgrupo de índice 2 de $\mathbf {Z} /n\ \mathbf {Z}$ para $n$ pares e a todo o grupo $\mathbf {Z} /n\ \mathbf {Z}$ quando $n$ é ímpar:

Z/n Z× + Z/n Z× = Z/n Z ou 2Z/n Z.

Encontrando raízes primitivas

Nenhuma fórmula geral simples para calcular raízes primitivas módulo $n$ é conhecida. No entanto, existem métodos para localizar uma raiz primitiva que são mais rápidos do que simplesmente tentar todos os candidatos. Se a ordem multiplicativa de um número $m$ módulo $n$ for igual a $\varphi (n)$ (a ordem de $\mathbf {Z} _{n}^{x}$), então é uma raiz primitiva. Na verdade, o inverso é verdadeiro: se $m$ é uma raiz primitiva módulo $n$, então a ordem multiplicativa de $m$ é $\varphi (n)$. Podemos usar isso para testar um candidato $m$ para ver se ele é primitivo.

Primeiro, calcule $\varphi (n)$. Em seguida, determine os diferentes fatores primos de $\varphi (n)$, digamos $p_{1},...,p_{k}$. Finalmente, calcule

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

usando um algoritmo rápido para exponenciação modular, como exponenciação binária. Um número $m$ para o qual esses resultados $k$ são todos diferentes de 1 é uma raiz primitiva.

O número de raízes primitivas módulo $n$, se houver, é igual a

$\varphi \left(\varphi (n)\right)$

uma vez que, em geral, um grupo cíclico com $r$ elementos tem $\varphi (r)$ geradores. Para o primo $n$, isso é igual $\varphi (n-1)$, e já que $n/\varphi (n-1)\in O(\log \log n)$ os geradores são muito comuns entre $\{2,...,n-1\}$ e, portanto, é relativamente fácil encontrar um.

Se $g$ é uma raiz primitiva módulo $p$, então $g$ também é uma raiz primitiva módulo todas as potências $p^{k}$ a menos que $g^{p-1}\equiv 1\ (\mathrm {mod} \ p^{2})$; nesse caso, $g+p$ é.

Se $g$ é uma raiz primitiva do módulo $p^{k}$, então $g$ ou $g+p^{k}$ (o que for ímpar) é uma raiz primitiva do módulo $2p^{k}$.

Encontrar raízes primitivas módulo $p$ também é equivalente a encontrar as raízes do ($p-1$)-ésimo polinomial ciclotômico módulo $p$.

Ordem de magnitude das raízes primitivas

A raiz menos primitiva $g_{p}$ módulo $p$ (no intervalo $1,2,...,p-1$) é geralmente pequena.

Limites superiores

Burgess (1962) provou que para cada $\epsilon >0$ existe um $C$ tal que $g_{p}\leq Cp^{{\frac {1}{4}}+\epsilon }.$

Grosswald (1981) provou que se $p>e^{e^{24}}$, então $g_{p}<p^{0.499}$.

Carella (2015) provou que existe um $C>0$ tal que $g_{p}\leq Cp^{5/\log \log p}$ para todos os primos suficientemente grandes $p>2$.

Shoup (1990, 1992) provou, assumindo a hipótese generalizada de Riemann, que $g_{p}=\mathrm {O} (\log ^{6}p)$.

Limites inferiores

Fridlander (1949) e Salié (1950) provaram que existe uma constante positiva $C$ tal que para um número infinito de números primos $g_{p}>C\log p$.

Pode ser provado de uma maneira elementar que para qualquer inteiro positivo $M$ existem infinitos primos tais que $M<g_{p}<p-M$.

Aplicações

Uma raiz primitiva módulo $n$ é frequentemente usado em criptografia, incluindo o esquema de troca de chaves Diffie–Hellman. Os difusores de som têm sido baseados em conceitos da teoria dos números, como raízes primitivas e resíduos quadráticos.

Referências

O Disquisitiones Arithmeticae foi traduzido do latim ciceroniano de Gauss para o inglês e o alemão. A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática, a determinação do sinal da soma de Gauss, as investigações sobre a reciprocidade biquadrática e notas não publicadas.

• Amiot, Emmanuel (2016), Music Through Fourier Space, ISBN 978-3-319-45581-5, Zürich: Springer .
• Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), ISBN 978-0-262-02405-1, Cambridge: The MIT Press .
• Carella, N. A. (2015), «Least Prime Primitive Roots», International Journal of Mathematics and Computer Science, 10 (2): 185-194, arXiv:1709.01172 .
• Cohen, Henri (1993), A Course in Computational Algebraic Number Theory, ISBN 978-3-540-55640-4, Berlin: Springer .
• Gauss, Carl Friedrich; Clarke, Arthur A. (translator) (1986), Disquisitiones Arithmeticae, ISBN 978-0-387-96254-2 2nd, corrected ed. , New York: Springer  [in English].
• Gauss, Carl Friedrich; Maser, H. (translator) (1965), Untersuchungen über höhere Arithmetik [Studies on higher arithmetic], ISBN 978-0-8284-0191-3 2nd ed. , New York: Chelsea  [em alemão].
• Ribenboim, Paulo (1996), The New Book of Prime Number Records, ISBN 978-0-387-94457-9, New York: Springer .
• Robbins, Neville (2006), Beginning Number Theory, ISBN 978-0-7637-3768-9, Jones & Bartlett Learning .
• Vinogradov, I. M. (2003), «§ VI PRIMITIVE ROOTS AND INDICES», Elements of Number Theory, ISBN 978-0-486-49530-9, Mineola, NY: Dover Publications, pp. 105–121 .
• von zur Gathen, Joachim; Shparlinski, Igor (1998), «Orders of Gauss periods in finite fields», Applicable Algebra in Engineering, Communication and Computing, 9 (1): 15–24, CiteSeerX 10.1.1.46.5504, MR 1624824, doi:10.1007/s002000050093 .

Leitura adicional

• Ore, Oystein (1988), Number Theory and Its History, ISBN 978-0-486-65620-5, Dover, pp. 284–302 .

Ligações externas

• Weisstein, Eric W. «Primitive Root». MathWorld (em inglês) 
• Quadratic Residues and Primitive Roots" - Michigan Tech
• Primitive Roots Calculator - BlueTulip