Raiz primitiva módulo n

Na aritmética modular, um ramo da teoria dos números, um número ${\displaystyle g}$ é uma raiz primitiva módulo n se todo número ${\displaystyle a}$ coprimo a ${\displaystyle n}$ for congruente com uma potência de ${\displaystyle g}$ módulo ${\displaystyle n}$. Ou seja, ${\displaystyle g}$ é uma raiz primitiva módulo ${\displaystyle n}$ se para cada inteiro ${\displaystyle a}$ coprimo com ${\displaystyle n}$, existe um inteiro ${\displaystyle k}$ tal que ${\displaystyle g^{k}\equiv a\ (\mathrm {mod} \ n)}$. Esse valor ${\displaystyle k}$ é chamado de índice ou logaritmo discreto de ${\displaystyle a}$ para a base ${\displaystyle g}$ módulo ${\displaystyle n}$. Observe que ${\displaystyle g}$ é uma raiz primitiva do módulo ${\displaystyle n}$ se e somente se ${\displaystyle 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 ${\displaystyle 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^[1] porque

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

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 (${\displaystyle g^{k}}$ módulo ${\displaystyle n}$) sempre se repete após algum valor de ${\displaystyle k}$, uma vez que o módulo ${\displaystyle n}$ produz um número finito de valores. Se ${\displaystyle g}$ for uma raiz primitiva módulo ${\displaystyle n}$ e ${\displaystyle n}$ for primo, o período de repetição será ${\displaystyle n-1}$. Curiosamente, as permutações criadas dessa maneira (e seus deslocamentos circulares) mostraram ser matrizes de Costas.

Definição

Se ${\displaystyle n}$ for um inteiro positivo, os inteiros entre ${\displaystyle 0}$ e ${\displaystyle n-1}$ que são coprimos com ${\displaystyle n}$ (ou equivalentemente, as classes de congruência coprimos com ${\displaystyle n}$) formam um grupo, com multiplicação módulo ${\displaystyle n}$ como operação; é denotado por ${\displaystyle \mathbf {Z} _{n}^{x}}$, e é chamado de grupo de unidades módulo ${\displaystyle n}$, ou grupo de classes primitivas módulo ${\displaystyle n}$. Conforme explicado no artigo grupo multiplicativo de inteiros módulo n, este grupo multiplicativo (${\displaystyle \mathrm {Z} _{n}^{x}}$) é cíclico se e somente se ${\displaystyle n}$ for igual a ${\displaystyle 2}$, ${\displaystyle 4}$, ${\displaystyle p^{k}}$ ou ${\displaystyle 2p^{k}}$, onde ${\displaystyle p^{k}}$ é uma potência de um número primo ímpar.^[2][3][4] Quando (e somente quando) este grupo ${\displaystyle \mathrm {Z} _{n}^{x}}$ é cíclico, um gerador deste grupo cíclico é chamado de raiz primitiva módulo n^[5] (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 ${\displaystyle X^{m}-1}$ no anel ${\displaystyle \mathbf {Z} _{n}}$), ou simplesmente um elemento primitivo de ${\displaystyle \mathbf {Z} _{n}^{x}}$. Quando ${\displaystyle \mathrm {Z} _{n}^{x}}$ é não-cíclico, tais elementos primitivos mod ${\displaystyle n}$ não existem.

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

Exemplos

Por exemplo, se ${\displaystyle n=14}$, então os elementos de ${\displaystyle \mathbf {Z} _{14}^{x}}$ são as classes de congruência ${\displaystyle \{1,3,5,9,11,13\}}$; existem ${\displaystyle \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 ${\displaystyle n=15}$. Os elementos de ${\displaystyle \mathbf {Z} _{15}^{x}}$ são as classes de congruência ${\displaystyle \{1,2,4,7,8,11,13,14\}}$; existem ${\displaystyle \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, ${\displaystyle \lambda (15)=4}$, onde ${\displaystyle \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 ${\displaystyle 11}$, ${\displaystyle 2}$ é dado como a raiz primitiva e na coluna ${\displaystyle 5}$ a entrada é ${\displaystyle 4}$. Isso significa que ${\displaystyle 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 ${\displaystyle 11}$, o índice de ${\displaystyle 6}$ é a soma dos índices para ${\displaystyle 2}$ e ${\displaystyle 3}$: ${\displaystyle 2^{1+8}=512\equiv 6\ (\mathrm {mod} \ 11)}$. O índice de ${\displaystyle 25}$ é o dobro do índice ${\displaystyle 5}$: ${\displaystyle 2^{8}=256\equiv 25\ (\mathrm {mod} \ 11)}$. (Claro, como ${\displaystyle 25\equiv 3\ (\mathrm {mod} \ 11)}$, a entrada para ${\displaystyle 3}$ é ${\displaystyle 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 ${\displaystyle \equiv 5}$ ou ${\displaystyle 1\ (\mathrm {mod} \ 8)}$; as colunas encabeçadas por números ${\displaystyle \equiv 3}$ ou ${\displaystyle 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 ${\displaystyle 32}$ o índice para ${\displaystyle 7}$ é ${\displaystyle 2}$ e ${\displaystyle 5^{2}=25\equiv -7\ (\mathrm {mod} \ 32)}$, mas a entrada para ${\displaystyle 17}$ é ${\displaystyle 4}$ e ${\displaystyle 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 ${\displaystyle n}$ para ${\displaystyle n\leq 72}$:

${\displaystyle n}$	raízes primitivas módulo ${\displaystyle n}$	ordem (OEIS: A000010)	${\displaystyle n}$	raízes primitivas módulo ${\displaystyle 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 ${\displaystyle a}$ que não é um quadrado perfeito nem ${\displaystyle -1}$ é uma raiz primitiva módulo infinitos primos.

A sequência de menores raízes primitivas módulo ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle >n}$ com raiz primitiva ${\displaystyle 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 ${\displaystyle n}$) com raiz primitiva ${\displaystyle 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^[6] que para qualquer número primo ${\displaystyle p}$ (com a única exceção de ${\displaystyle p=3}$), o produto de suas raízes primitivas é congruente a ${\displaystyle 1}$ módulo ${\displaystyle p}$.

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

Por exemplo,

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

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

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

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

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

${\displaystyle 3\times 11=33\equiv 2}$

${\displaystyle 12\times 13=156\equiv 1}$

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

${\displaystyle (-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 ${\displaystyle \mathbf {Z} /n\ \mathbf {Z} }$ para ${\displaystyle n}$ pares e a todo o grupo ${\displaystyle \mathbf {Z} /n\ \mathbf {Z} }$ quando ${\displaystyle n}$ é ímpar:

Z/n Z× + Z/n Z× = Z/n Z ou 2Z/n Z.[8]

Encontrando raízes primitivas

Nenhuma fórmula geral simples para calcular raízes primitivas módulo ${\displaystyle n}$ é conhecida.^[9][10] 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 ${\displaystyle m}$ módulo ${\displaystyle n}$ for igual a ${\displaystyle \varphi (n)}$ (a ordem de ${\displaystyle \mathbf {Z} _{n}^{x}}$), então é uma raiz primitiva. Na verdade, o inverso é verdadeiro: se ${\displaystyle m}$ é uma raiz primitiva módulo ${\displaystyle n}$, então a ordem multiplicativa de ${\displaystyle m}$ é ${\displaystyle \varphi (n)}$. Podemos usar isso para testar um candidato ${\displaystyle m}$ para ver se ele é primitivo.

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

${\displaystyle 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 ${\displaystyle m}$ para o qual esses resultados ${\displaystyle k}$ são todos diferentes de 1 é uma raiz primitiva.

O número de raízes primitivas módulo ${\displaystyle n}$, se houver, é igual a^[11]

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

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

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

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

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

Ordem de magnitude das raízes primitivas

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

Limites superiores

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

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

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

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

Limites inferiores

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

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

Aplicações

Uma raiz primitiva módulo ${\displaystyle 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.^[17][18]

Notas

1. «Archived copy». Consultado em 3 de julho de 2017. Arquivado do original em 3 de julho de 2017 
2. Weisstein, Eric W. «Modulo Multiplication Group». MathWorld (em inglês) 
3. Primitive root, Encyclopedia of Mathematics.
4. Vinogradov 2003, § VI PRIMITIVE ROOTS AND INDICES, pp. 105–121.
5. Vinogradov 2003, p. 106.
6. Gauss & Clarke 1986, arts. 80.
7. Gauss & Clarke 1986, arts. 81.
8. Emmanuel Amiot, Music Through Fourier Space, p. 38 (Springer, CMS Series, 2016).
9. von zur Gathen & Shparlinski 1998, pp. 15–24: "One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots."
10. Robbins 2006, p. 159: "There is no convenient formula for computing [the least primitive root]."
11. (sequência A010554 na OEIS)
12. Donald E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).
13. Cohen 1993, p. 26.
14. Ribenboim 1996, p. 24.
15. Carella, N. A. (2015). «Least Prime Primitive Roots». International Journal of Mathematics and Computer Science. 10 (2): 185-194. arXiv:1709.01172 
16. Bach & Shallit 1996, p. 254.
17. Walker, R. «The design and application of modular acoustic diffusing elements» (PDF). BBC Research Department. Consultado em 25 de março de 2019 
18. Feldman, Eliot (julho de 1995). «A reflection grating that nullifies the specular reflection: A cone of silence». J. Acoust. Soc. Am. 98 (1): 623–634. Bibcode:1995ASAJ...98..623F. doi:10.1121/1.413656 

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

• Portal da matemática