Mostrar código-fonte de Raiz primitiva módulo n

Na [[aritmética modular]], um ramo da [[teoria dos números]], um número <math>g</math> é uma '''raiz primitiva módulo ''n''''' se todo número <math>a</math> [[Números primos entre si|coprimo]] a <math>n</math> for [[Relação de congruência|congruente]] com uma [[Exponenciação|potência]] de <math>g</math> [[Aritmética modular|módulo]] <math>n</math>. Ou seja, <math>g</math> é uma raiz primitiva módulo <math>n</math> se para cada inteiro <math>a</math> coprimo com <math>n</math>, existe um inteiro <math>k</math> tal que <math>g^k \equiv a \ (\mathrm{mod} \ n)</math>. Esse valor <math>k</math> é chamado de '''índice''' ou '''[[logaritmo discreto]]''' de <math>a</math> para a base <math>g</math> módulo <math>n</math>. Observe que <math>g</math> é uma raiz primitiva do módulo <math>n</math> [[se e somente se]] <math>g</math> é um gerador do '''grupo multiplicativo de inteiros módulo ''n'''''.

[[Carl Friedrich Gauss|Gauss]] definiu raízes primitivas no Artigo 57 do ''[[Disquisitiones Arithmeticae]]'' (1801), onde ele atribuiu a [[Leonhard Euler|Euler]] a cunhagem do termo. No Artigo 56, ele afirmou que [[Johann Heinrich Lambert|Lambert]] e Euler sabiam deles, mas ele foi o primeiro a demonstrar rigorosamente que raízes primitivas existem para um <math>n</math> [[Número primo|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 é [[Prova construtiva|construtiva]].

== Exemplo elementar ==
O número 3 é uma raiz primitiva módulo 7<ref>{{citar web|url=http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |título=Archived copy |acessodata=2017-07-03 |arquivourl=https://web.archive.org/web/20170703173446/http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |arquivodata=2017-07-03 |urlmorta= sim}}</ref> porque
::<math>
\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}
</math>

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

== Definição ==

Se <math>n</math> for um inteiro positivo, os inteiros entre <math>0</math> e <math>n - 1</math> que são [[Números primos entre si|coprimos]] com <math>n</math> (ou equivalentemente, as [[Classe de congruência|classes de congruência]] coprimos com <math>n</math>) formam um [[Grupo (matemática)|grupo]], com multiplicação [[Aritmética modular|módulo]] <math>n</math> como operação; é denotado por <math>\mathbf{Z}_n^x</math>, e é chamado de [[Unidade (teoria dos anéis)|grupo de unidades]] módulo <math>n</math>, ou grupo de classes primitivas módulo <math>n</math>. Conforme explicado no artigo '''grupo multiplicativo de inteiros módulo ''n''''', este grupo multiplicativo (<math>\mathrm{Z}_n^x</math>) é [[Grupo cíclico|cíclico]] '''se e somente se''' <math>n</math> for igual a <math>2</math>, <math>4</math>, <math>p^k</math> ou <math>2p^k</math>, onde <math>p^k</math> é uma potência de um [[número primo]] [[ímpar]].<ref>{{MathWorld|title=Modulo Multiplication Group|urlname=ModuloMultiplicationGroup}}
</ref><ref>[http://www.encyclopediaofmath.org/index.php/Primitive_root Primitive root], [[Encyclopedia of Mathematics]].</ref><ref name="Vinogradov2003.pp=105–121">{{Harvnb|Vinogradov|2003|loc=&sect; VI PRIMITIVE ROOTS AND INDICES|pp=105–121}}.</ref> Quando (e somente quando) este grupo <math>\mathrm{Z}_n^x</math> é cíclico, um [[Conjunto gerador de um grupo|gerador]] deste grupo cíclico é chamado de '''raiz primitiva módulo ''n'''''<ref>{{Harvnb|Vinogradov|2003|p=106}}.</ref> (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]] <math>X^m- 1</math> no anel <math>\mathbf{Z}_n</math>), ou simplesmente um '''elemento primitivo de''' <math>\mathbf{Z}_n^x</math>. Quando <math>\mathrm{Z}_n^x</math> é não-cíclico, tais elementos primitivos mod <math>n</math> não existem.

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

== Exemplos ==

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

  x     x, x<sup>2</sup>, x<sup>3</sup>, ... (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 <math>n = 15</math>. Os elementos de <math>\mathbf{Z}_{15}^x</math> são as classes de congruência <math>\{1, 2, 4, 7, 8, 11, 13, 14\}</math>; existem <math>\varphi (15) = 8</math> deles.

  x     x, x<sup>2</sup>, x<sup>3</sup>, ... (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 multiplicativa|ordem]] seja 8, não há raízes primitivas módulo 15. De fato, <math>\lambda (15) = 4</math>, onde <math>\lambda</math> é a [[função de Carmichael]]. {{OEIS|id=A002322}}

=== 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, ... {{OEIS|id=A033948}}

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úmero racional|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.
<blockquote>Por exemplo, na linha <math>11</math>, <math>2</math> é dado como a raiz primitiva e na coluna <math>5</math> a entrada é <math>4</math>. Isso significa que <math>2^4 = 16 \equiv 5 \ (\mathrm{mod}\ 11)</math>. </blockquote>
Para o índice de um [[número composto]], some os índices de seus fatores primos.<blockquote>Por exemplo, na linha <math>11</math>, o índice de <math>6</math> é a soma dos índices para <math>2</math> e <math>3</math>: <math>2^{1 + 8} = 512 \equiv 6\ (\mathrm{mod}\ 11)</math>. O índice de <math>25</math> é o dobro do índice <math>5</math>: <math>2^{8} = 256 \equiv 25\ (\mathrm{mod}\ 11)</math>. (Claro, como <math>25 \equiv 3\ (\mathrm{mod}\ 11)</math>, a entrada para <math>3</math> é <math>8</math>).</blockquote>

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 <math>\equiv 5</math> ou <math>1\ (\mathrm{mod}\ 8)</math>; as colunas encabeçadas por números <math>\equiv 3</math> ou <math>7\ (\mathrm{mod}\ 8)</math> contêm o índice de seu negativo. {{OEIS|A185189}} e {{OEIS|A185268}}<blockquote>Por exemplo, no módulo <math>32</math> o índice para <math>7</math> é <math>2</math> e <math>5^{2} = 25 \equiv -7\ (\mathrm{mod}\ 32)</math>, mas a entrada para <math>17</math> é <math>4</math> e <math>5^{4} = 625 \equiv 17\ (\mathrm{mod}\ 32)</math>.</blockquote>

{|  class="wikitable" style="text-align:center" cellpadding="2"
|+Raízes primitivas e índices<br/>(outras colunas são os índices de inteiros sob os respectivos títulos das colunas)
|-
! width="25" | ''n''
! width="25" | raiz
! width="25" | 2
! width="25" | 3
! width="25" | 5
! width="25" | 7
! width="25" | 11
| width="10" rowspan="34" | &nbsp;
! width="25" | 13
! width="25" | 17
! width="25" | 19
! width="25" | 23
! width="25" | 29
| width="10" rowspan="34" | &nbsp;
! width="25" | 31
! width="25" | 37
! width="25" | 41
! width="25" | 43
! width="25" | 47
| width="10" rowspan="34" | &nbsp;
! width="25" | 53
! width="25" | 59
! width="25" | 61
! width="25" | 67
! width="25" | 71
| width="10" rowspan="34" | &nbsp;
! width="25" | 73
! width="25" | 79
! width="25" | 83
! width="25" | 89
! width="25" | 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
|
|-
! width="25" | ''n''
! width="25" | raiz
! width="25" | 2
! width="25" | 3
! width="25" | 5
! width="25" | 7
! width="25" | 11
! width="25" | 13
! width="25" | 17
! width="25" | 19
! width="25" | 23
! width="25" | 29
! width="25" | 31
! width="25" | 37
! width="25" | 41
! width="25" | 43
! width="25" | 47
! width="25" | 53
! width="25" | 59
! width="25" | 61
! width="25" | 67
! width="25" | 71
! width="25" | 73
! width="25" | 79
! width="25" | 83
! width="25" | 89
! width="25" | 97
|}

A tabela a seguir lista as raízes primitivas módulo <math>n</math> para <math>n \leq 72</math>:

{|class="wikitable"
!{{tmath|n}}
!raízes primitivas módulo {{tmath|n}}
!ordem
({{OEIS2C|A000010}})
!{{tmath|n}}
!raízes primitivas módulo {{tmath|n}}
!ordem
({{OEIS2C|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 raízes primitivas|conjectura de Artin sobre as raízes primitivas]] afirma que um dado inteiro <math>a</math> que não é um [[quadrado perfeito]] nem <math>-1</math> é uma raiz primitiva módulo infinitos [[Número primo|primos]].

A sequência de menores raízes primitivas módulo <math>n</math> (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, ... {{OEIS|id=A046145}}

Para <math>n</math> 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, ... {{OEIS|id=A001918}}

As maiores raízes primitivas módulo <math>n</math> 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, ... {{OEIS|id=A046146}}

Para <math>n</math> 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, ... {{OEIS|id=A071894}}

Número de raízes primitivas módulo <math>n</math> 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, ... {{OEIS|id=A046144}}

Para <math>n</math> 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, ... {{OEIS|id=A008330}}

Menor primo <math>> n</math> com raiz primitiva <math>n</math> 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, ... {{OEIS|id=A023049}}

Menor primo (não necessariamente excedendo <math>n</math>) com raiz primitiva <math>n</math> 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, ... {{OEIS|id=A056619}}

=== Fatos aritméticos ===

Gauss provou<ref>{{Harvnb|Gauss|Clarke|1986|loc=arts. 80}}.</ref> que para qualquer número primo <math>p</math> (com a única exceção de <math>p = 3</math>), o produto de suas raízes primitivas é congruente a <math>1</math> módulo <math>p</math>.

Ele também provou<ref>{{Harvnb|Gauss|Clarke|1986|loc=arts. 81}}.</ref> que para qualquer número primo <math>p</math>, a soma de suas raízes primitivas é congruente com <math>\mu (p - 1)</math> módulo <math>p</math>, onde <math>\mu</math> é a [[função de Möbius]].

<blockquote>Por exemplo,
:<math>p = 3</math>, <math>\mu (2)=-1</math>. A raiz primitiva é <math>2</math>.
:<math>p = 5</math>,  <math>\mu (4)=0</math>. The primitive roots are <math>2</math> and <math>3</math>.
:<math>p = 7</math>,  <math>\mu (6)=1</math>. The primitive roots are <math>3</math> and <math>5</math>.
:<math>p = 31</math>, <math>\mu (30)=-1</math>. The primitive roots are <math>3</math>, <math>11</math>, <math>12</math>, <math>13</math>, <math>17</math>, <math>21</math>, <math>22</math> e <math>24</math>.
::Seu produto <math>970377408 \equiv 1\ (\mathrm{mod}\ 31)</math> e sua soma <math>123 \equiv -1\ (\mathrm{mod}\ 31)</math>.

::<math>3 \times 11 = 33 \equiv 2</math>
::<math>12 \times 13 = 156 \equiv 1</math>
::<math>(-14) \times (-10) = 140 \equiv 16</math>
::<math>(-9) \times (-7) = 63 \equiv 1,\quad \text{e}\quad 2 \times 1 \times 16 \times 1 = 32 \equiv 1\ (\mathrm{mod}\ 31)</math>.

</blockquote>

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

== Encontrando raízes primitivas ==

Nenhuma fórmula geral simples para calcular raízes primitivas módulo <math>n</math> é conhecida.<ref>{{Harvnb|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."</ref><ref>{{Harvnb|Robbins|2006|p=159}}: "There is no convenient formula for computing [the least primitive root]."</ref> 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 <math>m</math> módulo <math>n</math> for igual a <math>\varphi (n)</math> (a ordem de <math>\mathbf{Z}_n^x</math>), então é uma raiz primitiva. Na verdade, o inverso é verdadeiro: se <math>m</math> é uma raiz primitiva módulo <math>n</math>, então a ordem multiplicativa de <math>m</math> é <math>\varphi (n)</math>. Podemos usar isso para testar um candidato <math>m</math> para ver se ele é primitivo.

Primeiro, calcule <math>\varphi (n)</math>. Em seguida, determine os diferentes fatores primos de <math>\varphi (n)</math>, digamos <math>p_1, ..., p_k</math>. Finalmente, calcule
:<math>m^{\varphi(n)/p_i}\bmod n \qquad\mbox{ para } i=1,\ldots,k</math>
usando um [[algoritmo]] rápido para [[exponenciação modular]], como [[exponenciação binária]]. Um número <math>m</math> para o qual esses resultados <math>k</math> são todos diferentes de 1 é uma raiz primitiva.

O número de raízes primitivas módulo <math>n</math>, se houver, é igual a<ref>{{OEIS|A010554}}</ref>
:<math>\varphi\left(\varphi(n)\right)</math>
uma vez que, em geral, um grupo cíclico com <math>r</math> elementos tem <math>\varphi(r)</math> geradores. Para o primo <math>n</math>, isso é igual <math>\varphi(n-1)</math>, e já que <math>n / \varphi(n-1) \in O(\log\log n)</math> os geradores são muito comuns entre <math>\{2, ..., n - 1\}</math> e, portanto, é relativamente fácil encontrar um.<ref>Donald E. Knuth, ''The Art of Computer Programming, vol. 2: Seminumerical Algorithms'', 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).</ref>

Se <math>g</math> é uma raiz primitiva módulo <math>p</math>, então <math>g</math> também é uma raiz primitiva módulo todas as potências <math>p^k</math> a menos que <math>g^{p-1} \equiv 1\ (\mathrm{mod}\ p^2)</math>; nesse caso, <math>g + p</math> é.<ref name="Cohen1993">{{Harvnb|Cohen|1993|p=26}}.</ref>

Se <math>g</math> é uma raiz primitiva do módulo <math>p^k</math>, então <math>g</math> ou <math>g + p^k</math> (o que for ímpar) é uma raiz primitiva do módulo <math>2p^k</math>.<ref name="Cohen1993"/>

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

== Ordem de magnitude das raízes primitivas ==

A raiz menos primitiva <math>g_p</math> módulo <math>p</math> (no intervalo <math>1, 2, ..., p - 1</math>) é geralmente pequena.

=== Limites superiores ===
Burgess (1962) provou<ref name="Ribenboim, p.24"/> que para cada <math>\epsilon> 0</math> existe um <math>C</math> tal que <math>g_p \leq Cp^{\frac{1}{4}+\epsilon}.</math>

Grosswald (1981) provou<ref name="Ribenboim, p.24"/> que se <math>p > e^{e^{24}}</math>, então <math>g_p < p^{0.499}</math>.

Carella (2015) provou<ref>{{citar periódico| arxiv=1709.01172 |título=Least Prime Primitive Roots |último1 =Carella |primeiro1 =N. A. |ano=2015 |periódico=International Journal of Mathematics and Computer Science | volume=10 |número=2 |páginas=185-194  }}</ref> que existe um <math> C >0 </math> tal que <math>g_p \leq Cp^{5/\log \log p}</math> para todos os primos suficientemente grandes <math> p>2</math>.

Shoup (1990, 1992) provou,<ref>{{Harvnb|Bach|Shallit|1996|p=254}}.</ref> assumindo a [[hipótese generalizada de Riemann]], que <math>g_p = \mathrm{O} (\log^6 p)</math>.

=== Limites inferiores ===
Fridlander (1949) e Salié (1950) provaram<ref name="Ribenboim, p.24">{{Harvnb|Ribenboim|1996|p=24}}.</ref> que existe uma constante positiva <math>C</math> tal que para um número infinito de números primos <math>g_p> C \log p</math>.

Pode ser provado<ref name="Ribenboim, p.24"/> de uma maneira elementar que para qualquer inteiro positivo <math>M</math> existem infinitos primos tais que <math>M <g_p <p - M</math>.

== Aplicações ==

Uma raiz primitiva módulo <math>n</math> é frequentemente usado em [[criptografia]], incluindo o [[Troca de chaves de Diffie–Hellman|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íduo quadrático|resíduos quadráticos]].<ref>{{citar web|último =Walker|primeiro =R|título=The design and application of modular acoustic diffusing elements|url=http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf|publicado=BBC Research Department|acessodata=25 de março de 2019}}</ref><ref name="Feldman">{{citar periódico|primeiro = Eliot |último = Feldman |título= A reflection grating that nullifies the specular reflection: A cone of silence |periódico= J. Acoust. Soc. Am. |data=julho de 1995 |volume = 98 |número= 1 |páginas= 623–634 |doi = 10.1121/1.413656 |bibcode = 1995ASAJ...98..623F}}</ref>

==Notas==
{{reflist|30em}}

== Referências ==
O ''[[Disquisitiones Arithmeticae]]'' foi traduzido do [[Latim clássico|latim ciceroniano]] de [[Carl Friedrich Gauss|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 [[Lei da reciprocidade quadrática|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.
*{{Citation
 |último1 = Amiot
 |primeiro1 = Emmanuel
 |autorlink = 
 |título= Music Through Fourier Space
 |publicado= Springer
 |local= Zürich
 |ano= 2016
 | isbn = 978-3-319-45581-5
}}.
*{{Citation
 |último1 = Bach
 |primeiro1 = Eric
 |último2 = Shallit
 |primeiro2 = Jeffrey
 |título= Algorithmic Number Theory (Vol I: Efficient Algorithms)
 |publicado= The MIT Press
 |local= Cambridge
 |ano= 1996
 | isbn = 978-0-262-02405-1
}}.
*{{Citation
 |último1 = Carella
 |primeiro1 = N. A.
 |título= Least Prime Primitive Roots
 |número= 2
 |páginas= 185-194
 |periódico= International Journal of Mathematics and Computer Science
  | volume = 10
 |ano= 2015
 | arxiv=1709.01172
 }}.
*{{Citation
 |último1 = Cohen
 |primeiro1 = Henri
 |autorlink = 
 |título= A Course in Computational Algebraic Number Theory
 |publicado= [[Springer Science+Business Media|Springer]]
 |local= Berlin
 |ano= 1993
 | isbn = 978-3-540-55640-4
}}.
*{{Citation
 |último1 = Gauss
 |primeiro1 = Carl Friedrich
 | authorlink1 = Carl Friedrich Gauss
 |último2 = Clarke
 |primeiro2 = Arthur A. (translator)
 |título= Disquisitiones Arithmeticae
 |edição= 2nd, corrected
 |publicado= [[Springer Science+Business Media|Springer]]
 |local= New York
 |ano= 1986
 | isbn = 978-0-387-96254-2
}} [in English].
*{{Citation
 |último1 = Gauss
 |primeiro1 = Carl Friedrich
 | authorlink1 = Carl Friedrich Gauss
 |último2 = Maser
 |primeiro2 = H. (translator)
 |título= Untersuchungen über höhere Arithmetik [Studies on higher arithmetic]
 |edição= 2nd
 |publicado= Chelsea
 |local= New York
 |ano= 1965
 | isbn = 978-0-8284-0191-3
}} [em alemão].
*{{Citation
 |último = Ribenboim
 |primeiro = Paulo
 |autorlink = Paulo Ribenboim
 |título= The New Book of Prime Number Records
 |publicado= [[Springer Science+Business Media|Springer]]
 |local= New York
 |ano= 1996
 | isbn = 978-0-387-94457-9
}}.
*{{Citation
 |primeiro = Neville
 |último = Robbins
 |título= Beginning Number Theory
 |publicado= Jones & Bartlett Learning
 |ano= 2006
 | isbn = 978-0-7637-3768-9
 | url = https://books.google.com/books?id=TtLMrKDsDuIC&pg=PA159
}}.
*{{Citation
 |último1 = Vinogradov
 |primeiro1 = I. M.
 |autorlink1 = 
 |título= Elements of Number Theory
 |publicado= Dover Publications
 |local= Mineola, NY
 |ano= 2003
 | isbn = 978-0-486-49530-9
 |capítulo= &sect; VI PRIMITIVE ROOTS AND INDICES
 | pp = 105–121
 |capítulourl= https://books.google.co.jp/books?id=xlIfdGPM9t4C&lpg=PR3&hl=ja&pg=PA105#v=onepage&q&f=false
}}.
*{{Citation
 |último1 = von zur Gathen
 |primeiro1 = Joachim
 |autorlink1 = Joachim von zur Gathen
 |último2 = Shparlinski
 |primeiro2 = Igor
 |título= Orders of Gauss periods in finite fields
 |número= 1
 |páginas= 15–24
 |periódico= Applicable Algebra in Engineering, Communication and Computing
 | mr = 1624824
 | doi = 10.1007/s002000050093
 | volume = 9
 |ano= 1998
 | citeseerx = 10.1.1.46.5504
 }}.

==Leitura adicional==

*{{Citation
 |último = Ore
 |primeiro = Oystein
 |autorlink = Øystein Ore
 |título= Number Theory and Its History
 |publicado= Dover
 |ano= 1988
 |páginas= [https://archive.org/details/numbertheoryitsh0000orey/page/284 284–302]
 | isbn = 978-0-486-65620-5
 | url = https://archive.org/details/numbertheoryitsh0000orey/page/284
 }}.

==Ligações externas==
*{{MathWorld | title = Primitive Root | id = PrimitiveRoot}}
*{{URL|http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/quadratic4.html|Quadratic Residues and Primitive Roots" - Michigan Tech}}
*{{URL|http://www.bluetulip.org/programs/primitive.html|Primitive Roots Calculator - BlueTulip}}

{{Portal3|Matemática}}
{{DISPLAYTITLE:Raiz primitiva módulo ''n''}}
[[Categoria:Teoria dos números]]
[[Categoria:Aritmética modular]]