Na aritmética modular, um ramo da teoria dos números, um número é uma raiz primitiva módulo n se todo número coprimo a for congruente com uma potência de módulo . Ou seja, é uma raiz primitiva módulo se para cada inteiro coprimo com , existe um inteiro tal que . Esse valor é chamado de índice ou logaritmo discreto de para a base módulo . Observe que é uma raiz primitiva do módulo se e somente se é 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 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

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

Definição

Se for um inteiro positivo, os inteiros entre e que são coprimos com (ou equivalentemente, as classes de congruência coprimos com ) formam um grupo, com multiplicação módulo como operação; é denotado por , e é chamado de grupo de unidades módulo , ou grupo de classes primitivas módulo . Conforme explicado no artigo grupo multiplicativo de inteiros módulo n, este grupo multiplicativo () é cíclico se e somente se for igual a , , ou , onde é uma potência de um número primo ímpar.Primitive root, Encyclopedia of Mathematics.. Quando (e somente quando) este grupo é 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 no anel ), ou simplesmente um elemento primitivo de . Quando é não-cíclico, tais elementos primitivos mod não existem.

Para qualquer (seja ou não cíclico), a ordem de (ou seja, o número de elementos em) é dada pela função totiente de Euler . E então, o teorema de Euler diz que para todo coprimo com ; a menor potência de que é congruente a é chamada de ordem multiplicativa de módulo . Em particular, para ser uma raiz primitiva módulo , tem que ser a menor potência de que é congruente a .

Exemplos

Por exemplo, se , então os elementos de são as classes de congruência ; existem 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 . Os elementos de são as classes de congruência ; existem 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, , onde é a função de Carmichael.

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, ...

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 , é dado como a raiz primitiva e na coluna a entrada é . Isso significa que . Para o índice de um número composto, some os índices de seus fatores primos.Por exemplo, na linha , o índice de é a soma dos índices para e : . O índice de é o dobro do índice : . (Claro, como , a entrada para é ).

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 ou ; as colunas encabeçadas por números ou contêm o índice de seu negativo. e Por exemplo, no módulo o índice para é e , mas a entrada para é e .

+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 para :

raízes primitivas módulo ordem ()raízes primitivas módulo ordem ()101372, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 3536211383, 13, 15, 21, 29, 33183223924432401652, 34416, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 3540652421273, 56433, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 344284442092, 564524103, 74465, 7, 11, 15, 17, 19, 21, 33, 37, 4322112, 6, 7, 810475, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45461244816132, 6, 7, 1112493, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 4742143, 56503, 13, 17, 23, 27, 33, 37, 472015851321685224173, 5, 6, 7, 10, 11, 12, 1416532, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 5152185, 116545, 11, 23, 29, 41, 4718192, 3, 10, 13, 14, 15185540208562421125736227, 13, 17, 1910583, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 5528235, 7, 10, 11, 14, 15, 17, 19, 20, 2122592, 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, 56582486016252, 3, 8, 12, 13, 17, 22, 2320612, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 5960267, 11, 15, 1912623, 11, 13, 17, 21, 43, 53, 5530272, 5, 11, 14, 20, 2318633628126432292, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 272865483086620313, 11, 12, 13, 17, 21, 22, 2430672, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63663216683233206944343, 5, 7, 11, 23, 27, 29, 311670243524717, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 697036127224

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

A sequência de menores raízes primitivas módulo (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, ...

Para 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, ...

As maiores raízes primitivas módulo 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, ...

Para 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, ...

Número de raízes primitivas módulo 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, ...

Para 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, ...

Menor primo com raiz primitiva 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, ...

Menor primo (não necessariamente excedendo ) com raiz primitiva 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, ...

Fatos aritméticos

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

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

Por exemplo, , . A raiz primitiva é . , . The primitive roots are and . , . The primitive roots are and . , . The primitive roots are , , , , , , e . Seu produto e sua soma .

.

As somas (ou diferenças) de duas raízes primitivas somam todos os elementos do subgrupo de índice 2 de para pares e a todo o grupo quando é ímpar: Z/n Z× + Z/n Z× = Z/n Z ou 2Z/n Z.Emmanuel Amiot, Music Through Fourier Space, p. 38 (Springer, CMS Series, 2016).

Encontrando raízes primitivas