Ver o código fonte de «Raíz primitiva módulo n»

En [[aritmética modular]], un número {{Mvar|g}} é unha '''raíz primitiva módulo {{Mvar|n}}''' se todo número {{Mvar|a}} [[Números primos entre si|coprimo]] con {{Mvar|n}} é [[Relación de congruencia|congruente]] cunha potencia de {{Mvar|g}} módulo {{Mvar|n}}. É dicir, {{Mvar|g}} é unha ''raíz primitiva módulo'' {{Mvar|n}} se para cada número enteiro {{Mvar|a}} coprimo con {{Mvar|n}}, hai algún número enteiro {{Mvar|k}} para o cal {{Mvar|g}}<sup>{{Mvar|k}}</sup> ≡ {{Mvar|a}} (mod {{Mvar|n}}). Tal valor {{Mvar|k}} chámase '''índice''' ou '''logaritmo discreto''' de {{Mvar|a}} para a base {{Mvar|g}} módulo {{Mvar|n}}. Polo que {{Mvar|g}} é unha ''raíz primitiva módulo'' {{Mvar|n}} se e só se {{Mvar|g}} é un [[conxunto xerador dun grupo|xerador]] do [[grupo multiplicativo de enteiros módulo n]], denotado <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>.

Existe unha raíz primitiva se e só se ''n'' é 1, 2, 4, ''p''<sup>''k''</sup> ou 2''p''<sup>''k''</sup>, onde ''p'' é un primo impar e {{Nowrap|''k'' > 0}}. Para todos os demais valores de ''n'' o grupo multiplicativo de enteiros módulo ''n'' non é [[Grupo cíclico|cíclico]].<ref>{{MathWorld|title=Modulo Multiplication Group|urlname=ModuloMultiplicationGroup}}
</ref><ref name=":0">{{Cita web |title=Primitive root - Encyclopedia of Mathematics |url=https://encyclopediaofmath.org:443/wiki/Primitive_root |access-date=2024-11-05 |website=encyclopediaofmath.org}}</ref><ref name="Vinogradov2003.pp=105-121">{{Harv|Vinogradov|2003|loc=§ VI PRIMITIVE ROOTS AND INDICES|pp=105–121}}</ref>
Isto foi probado por primeira vez por [[Carl Friedrich Gauss|Gauss]].<ref>{{Harv|Gauss|1986|loc=arts. 52–56, 82–891}}</ref>

== Exemplo elemental ==
O número 3 é unha raíz primitiva módulo 7<ref>{{cita web |last=Stromquist |first=Walter |title=What are primitive roots? |publisher=Bryn Mawr College |department=Mathematics |url=http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |access-date=2017-07-03 |archive-url=https://web.archive.org/web/20170703173446/http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html |archive-date=2017-07-03}}</ref> porque 
:<math display="block">
\begin{array}{rcrcrcrcrcr}
3^1 &=& 3^0 \times 3 &\equiv& 1 \times 3 &=& 3 &\equiv& 3 \pmod 7 \\
3^2 &=& 3^1 \times 3 &\equiv& 3 \times 3 &=& 9 &\equiv& 2 \pmod 7 \\
3^3 &=& 3^2 \times 3 &\equiv& 2 \times 3 &=& 6 &\equiv& 6 \pmod 7 \\
3^4 &=& 3^3 \times 3 &\equiv& 6 \times 3 &=& 18 &\equiv& 4 \pmod 7 \\
3^5 &=& 3^4 \times 3 &\equiv& 4 \times 3 &=& 12 &\equiv& 5 \pmod 7 \\
3^6 &=& 3^5 \times 3 &\equiv& 5 \times 3 &=& 15 &\equiv& 1 \pmod 7
\end{array}
</math>

Aquí vemos que o [[Orde (teoría de grupos)|período]] de 3<sup>{{Mvar|k}}</sup> módulo 7 é 6. Os residuos do período, que son 3, 2, 6, 4, 5, 1, forman unha permutación de todos os restos distintos de cero módulo 7. Se {{Mvar|g}} é unha raíz primitiva módulo {{Mvar|n}} sendo {{Mvar|n}} primo, entón o período de repetición é {{Nowrap|{{mvar|n}} − 1.}} As permutacións creadas deste xeito (e os seus desprazamentos circulares) demostráronse como [[Matriz de Costas|matrices de Costas]].

== Definición ==
Se {{mvar|n}} é un enteiro positivo, os enteiros de 1 a {{nowrap|{{mvar|n}} − 1}} que son [[coprimo]]s con {{mvar|n}} (ou de forma equivalente, as [[aritmética modular#clases de congruencia|clases de congruencia]] coprimas con {{mvar|n}}) forman un [[grupo (matemáticas)|grupo]], coa multiplicación [[aritmética modular|módulo]] {{mvar|n}} como a súa operación; denótase como <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>, e chámase o [[grupo de unidades]] módulo {{mvar|n}}, ou o grupo de clases primitivas módulo {{mvar|n}}. Como se explica no artigo [[grupo multiplicativo de enteiros módulo n|grupo multiplicativo de enteiros módulo {{mvar|n}}]], este grupo multiplicativo <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> é [[grupo cíclico|cíclico]] '''se e só se''' {{mvar|n}} é igual a 2, 4, {{mvar|p{{sup|k}}}} ou 2{{mvar|p{{sup|k}}}} onde {{mvar|p{{sup|k}}}} é un potencia dun [[número primo]] impar.<ref>{{MathWorld |title=Modulo Multiplication Group |urlname=ModuloMultiplicationGroup}}
</ref><ref name=":0" /><ref name="Vinogradov2003.pp=105–121">{{Harvnb|Vinogradov|2003|loc=§ VI Primitive roots and indices|pp=105–121}}.</ref> Cando (e só cando) este grupo <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> é cíclico, un [[Conxunto xerador dun grupo|xerador]] deste grupo cíclico chámase '''raíz primitiva módulo {{mvar|n}}'''<ref>{{Harvnb|Vinogradov|2003|p=106}}.</ref> (ou en linguaxe máis completa '''raíz primitiva da unidade módulo {{mvar|n}}''', resaltando o seu papel como solución fundamental do polinomio de '''[[Raíz da unidade módulo n|raíces da unidade]]''' das ecuacións polinómicas X{{su|p={{mvar|m}}}} − 1 no anel <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>, ou simplemente un '''elemento primitivo de''' <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>.

Cando <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> non é cíclico, eses elementos primitivos mod {{Mvar|n}} non existen. Pola contra, cada compoñente primo de {{Mvar|n}} ten as súas propias raíces sub-primitivas (ver {{Math|15}} nos exemplos de abaixo).

Para calquera {{Mvar|n}} (sexa ou non <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> cíclico), a orde de  <math>(\mathbb{Z}/n\mathbb{Z})^\times</math> vén dada pola [[función totiente de Euler]] {{Mvar|φ}} ({{Mvar|n}}) {{OEIS|id=A000010}}. E entón, o  [[teorema de Euler]] di que {{Nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup> ≡ 1 (mod {{mvar|n}})}} para todo {{Mvar|a}} coprimo con {{Mvar|n}}; a potencia máis baixa de {{Mvar|a}} que é congruente con 1 módulo {{Mvar|n}} chámase orde multiplicativa de {{Mvar|a}} módulo {{Mvar|n}}. En particular, para que {{Mvar|a}} sexa unha raíz primitiva módulo {{Mvar|n}}, {{Nowrap|{{mvar|a}}<sup>{{mvar|φ}}({{mvar|n}})</sup>}} ten que ser a potencia máis pequena de {{Mvar|a}} que sexa congruente con 1 módulo {{Mvar|n}}.

== Exemplos ==
Por exemplo, se {{Nowrap|{{mvar|n}} {{=}} 14}} entón os elementos de <math>(\mathbb{Z}/14\mathbb{Z})^\times</math> son as clases de congruencia {1, 3, 5, 9, 11, 13}; hai {{Nowrap|{{mvar|φ}}(14) {{=}} 6}} delas. Aquí temos unha táboa das súas potencias 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 orde de 1 é 1, as ordes de 3 e 5 son 6, as ordes de 9 e 11 son 3 e a orde de 13 é 2. Así, 3 e 5 son as raíces primitivas módulo 14.

Para un segundo exemplo imos ver {{nowrap|{{mvar|n}} {{=}} 15.}} Os elementos de <math>(\mathbb{Z}/15\mathbb{Z})^\times</math> son as clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hai {{nowrap|{{mvar|φ}}(15) {{=}} 8}} delas.
  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 non hai número ningún cuxa orde sexa 8, non hai raíces primitivas módulo 15. De feito, {{Nowrap|{{mvar|λ}}(15) {{=}} 4}}, onde {{Mvar|λ}} é a [[función de Carmichael]]. {{OEIS|id=A002322}}    

== Táboa de raíces primitivas ==
Os números <math>n</math> que teñen unha raíz primitiva son da forma

: <math>n \in \{1, 2, 4, p^k, 2 \cdot p^k \; \; | \; \; 2 < p \text{ primo}; \; k \in \mathbb{N}\} ,</math>
: = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. <ref>{{Cita Harvard sen parénteses|Gauss|1986}}.</ref>

Estes son os números <math>n</math> con <math>\varphi(n) = \lambda(n),</math> {{OEIS|id=A033948}}.

A seguinte táboa enumera as raíces primitivas módulo {{Mvar|n}} ata <math>n=31</math>:
{| class="wikitable"
!{{Tmath|n}}
!raíces primitivas módulo {{Tmath|n}}
!orde  <math>\varphi(n),</math><br/>(OEIS: A000010)
![[Grupo de torsión|expoñente]] <math>\lambda(n),</math>(OEIS: A002322)
|-
|1
|0
|1
|1
|-
|2
|1
|1
|1
|-
|3
|2
|2
|2
|-
|4
|3
|2
|2
|-
|5
|2, 3
|4
|4
|-
|6
|5
|2
|2
|-
|7
|3, 5
|6
|6
|-
|8
|
|4
|2
|-
|9
|2, 5
|6
|6
|-
|10
|3, 7
|4
|4
|-
|11
|2, 6, 7, 8
|10
|10
|-
|12
|
|4
|2
|-
|13
|2, 6, 7, 11
|12
|12
|-
|14
|3, 5
|6
|6
|-
|15
|
|8
|4
|-
|16
|
|8
|4
|-
|17
|3, 5, 6, 7, 10, 11, 12, 14
|16
|16
|-
|18
|5, 11
|6
|6
|-
|19
|2, 3, 10, 13, 14, 15
|18
|18
|-
|20
|
|8
|4
|-
|21
|
|12
|6
|-
|22
|7, 13, 17, 19
|10
|10
|-
|23
|5, 7, 10, 11, 14, 15, 17, 19, 20, 21
|22
|22
|-
|24
|
|8
|2
|-
|25
|2, 3, 8, 12, 13, 17, 22, 23
|20
|20
|-
|26
|7, 11, 15, 19
|12
|12
|-
|27
|2, 5, 11, 14, 20, 23
|18
|18
|-
|28
|
|12
|6
|-
|29
|2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
|28
|28
|-
|30
|
|8
|4
|-
|31
|3, 11, 12, 13, 17, 21, 22, 24
|30
|30
|}

== Propiedades ==
Gauss demostrou<ref>{{Cita Harvard sen parénteses|Gauss|1986}}</ref> que para calquera número primo {{Mvar|p}} (coa única excepción de {{Nowrap|{{mvar|p}} {{=}} 3),}} o produto das súas raíces primitivas é congruente con 1 módulo {{Mvar|p}}.

Tamén demostrou <ref>{{Cita Harvard sen parénteses|Gauss|1986}}.</ref> que para calquera número primo {{Mvar|p}}, a suma das súas raíces primitivas é congruente con {{Mvar|μ}}( {{Mvar|p}} − 1) módulo {{Mvar|p}}, onde {{Mvar|μ}} é a [[función de Möbius]].

Por exemplo,
:{|
|-
|{{mvar|p}} = 3, || {{mvar|μ}}(2) = −1. || A raíz primitiva é 2.
|-
|{{mvar|p}} = 5, || {{mvar|μ}}(4) = 0. || As raíces primitivas son  2 e 3.
|-
|{{mvar|p}} = 7, || {{mvar|μ}}(6) = 1. || As raíces primitivas son  3 e 5.
|-
|{{mvar|p}} = 31, ||{{mvar|μ}}(30) = −1. || As raíces primitivas son   3, 11, 12, 13, 17, 21, 22 e 24.
|}


Por exemplo, o produto destas últimas raíces primitivas é <math>2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}</math>, e a súa suma é <math>123 \equiv -1 \equiv \mu(31-1) \pmod{31}</math> .

[[Conxectura de Artin sobre raíces primitivas|A conxectura de Artin sobre as raíces primitivas]] afirma que un enteiro dado {{Mvar|a}} que non é nin un [[cadrado perfecto]] nin -1 é unha raíz primitiva módulo infinitamente moitos [[Número primo|primos]].

== Procurando raíces primitivas ==
Non se coñece unha fórmula xeral simple para calcular raíces primitivas módulo {{Mvar|n}} . {{Efn|"Un dos problemas sen resolver máis importantes na teoría de corpos finitos é o deseño dun algoritmo rápido para construír raíces primitivas.{{Harvnb|von zur Gathen|Shparlinski|1998|pp=15–24}}}} {{Efn|"Non hai unha fórmula conveniente para calcular a menor raíz primitiva." {{Harvnb|Robbins|2006|p=159}}}} No entanto, hai métodos para localizar unha raíz primitiva que son máis rápidos que simplemente probar todos os candidatos. Se a orde multiplicativa (o seu [[Grupo de torsión|expoñente]]) dun número {{Mvar|m}} módulo {{Mvar|n}} é igual a [[Función totiente de Euler|<math>\varphi(n)</math>]] (a orde de <math>(\mathbb{Z}/n\mathbb{Z})^\times</math>), entón é unha raíz primitiva. De feito, a inversa é verdade: se {{Mvar|m}} é unha raíz primitiva módulo {{Mvar|n}}, entón a orde multiplicativa de {{Mvar|m}} é <math>\varphi(n) = \lambda(n).</math> Podemos usalo para probar un candidato {{Mvar|m}} para ver se é primitivo.

Para <math>n > 1</math> primeiro, calcular <math>\varphi(n).</math> Despois determinar os diferentes [[Número primo|factores primos]] de <math>\varphi(n)</math>, digamos {{Mvar|p}}<sub>1</sub> ,... , {{Mvar|p{{sub|k}}}}. Finalmente, calcular

: <math>g^{\varphi(n)/p_i}\bmod n \qquad\mbox{ para } i=1,\ldots,k</math>

usando un algoritmo rápido para a [[exponenciación modular]] como a exponenciación por cadrado. Un número {{Mvar|g}} para o que estes {{Mvar|k}} resultados son todos diferentes de 1 é unha raíz primitiva.

O número de raíces primitivas módulo {{Mvar|n}}, se as hai, é igual a <ref>{{OEIS|id=A010554}}</ref>

: <math>\varphi\left(\varphi(n)\right)</math>

xa que, en xeral, un grupo cíclico con {{Mvar|r}} elementos ten <math>\varphi(r)</math> xeradores.

Para {{Mvar|n}} primo, isto é igual a <math>\varphi(n-1)</math>, e posto que <math>n / \varphi(n-1) \in O(\log\log n)</math> os xeradores son moi comúns entre {2, ..., {{Mvar|n}} &#x2212; 1} e, polo tanto, é relativamente fácil atopar un. 

Se {{Mvar|g}} é unha raíz primitiva módulo {{Mvar|p}}, entón {{Mvar|g}} é tamén unha raíz primitiva módulo todas as potencias {{Mvar|p{{sup|k}}}} a menos que {{Mvar|g}}<sup>{{Mvar|p}} −1</sup> ≡ 1 (mod {{Mvar|p}}<sup>2</sup>); nese caso temos que  {{Mvar|g}} + {{Mvar|p}} si o é. 

Se {{Mvar|g}} é unha raíz primitiva módulo {{Mvar|p{{sup|k}}}}, entón {{Mvar|g}} é tamén unha raíz primitiva módulo todas as potencias menores de {{Mvar|p}}.

Se {{Mvar|g}} é unha raíz primitiva módulo {{Mvar|p{{sup|k}}}}, entón {{Mvar|g}} ou {{Mvar|g}} + {{Mvar|p{{sup|k}}}} (o que sexa impar) é unha raíz primitiva módulo 2{{Mvar|p{{sup|k}}}}. 

Atopar raíces primitivas módulo {{Mvar|p}} tamén é equivalente a atopar as raíces do ({{Mvar|p}} − 1) polinomio ciclotómico módulo {{Mvar|p}}.

== Notas ==
{{reflist|30em}} 
{{Reflist|group=lower-alpha}} 
== Véxase tamén ==

=== Bibliografía ===
* {{cita libro
 | last1 = Bach     | first1 = Eric
 | last2 = Shallit  | first2 = Jeffrey
 | year = 1996
 | title = Efficient Algorithms
 | series = Algorithmic Number Theory  | volume = I
 | publisher = [[The MIT Press]]
 | location = Cambridge, MA
 | isbn = 978-0-262-02405-1
}}

* {{cita publicación periódica
 | last1 = Carella  | first1 = N. A.
 | year = 2015
 | title = Least Prime Primitive Roots
 | journal = International Journal of Mathematics and Computer Science
 | volume = 10  | issue = 2  | pages = 185–194
 | arxiv=1709.01172
 }}

*{{cita libro
 | last = Gauss | first = Carl Friedrich | author-link = Carl Friedrich Gauss
 | translator-last = Clarke  | translator-first = Arthur A.
 | orig-year = 1801  | year = 1986
 | title = Disquisitiones Arithmeticae   | edition = 2nd, corrected
 | publisher = [[Springer Science+Business Media|Springer]]
 | location = New York, NY
 | isbn = 978-0-387-96254-2
}}

*{{cita libro
 | last = Gauss | first = Carl Friedrich | author-link = Carl Friedrich Gauss
 | translator-last = Maser  | translator-first = H.
 | orig-year = 1801  | year = 1965
 | title = Untersuchungen über höhere Arithmetik   | edition = 2nd
 | trans-title = Studies of Higher Arithmetic
 | publisher = Chelsea
 | location = New York, NY
 | isbn = 978-0-8284-0191-3
}}

*{{cita libro
 | first = Neville  | last = Robbins
 | year = 2006
 | title = Beginning Number Theory
 | publisher = Jones & Bartlett Learning
 | isbn = 978-0-7637-3768-9
 | url = https://books.google.com/books?id=TtLMrKDsDuIC&pg=PA159
}}

*{{cita libro
 | last = Vinogradov  | first = I.M.
 | author-link = Ivan Matveyevich Vinogradov
 | year = 2003
 | title = Elements of Number Theory
 | chapter = §&nbsp;VI Primitive roots and indices
 | pages = 105–121
 | publisher = Dover Publications
 | location = Mineola, NY
 | isbn = 978-0-486-49530-9
 | chapter-url = https://books.google.com/books?id=xlIfdGPM9t4C&pg=PA105
}}

*{{cita publicación periódica
 | last1 = von zur Gathen  | first1 = Joachim
 | author1-link = Joachim von zur Gathen
 | last2 = Shparlinski  | first2 = Igor
 | year = 1998
 | title = Orders of Gauss periods in finite fields
 | journal = Applicable Algebra in Engineering, Communication and Computing
 | volume = 9  | issue = 1  | pages = 15–24
 | mr = 1624824  
 | doi = 10.1007/s002000050093
 }}
=== Outros artigos ===
* [[Caracter de Dirichlet]]
* [[Teorema de Wilson]]
* [[Residuo cadrático]]
* [[Raíz da unidade módulo n]]
* [[Conxectura de Artin sobre raíces primitivas]]
=== Ligazóns externas ===
* {{MathWorld
 | title = Primitive Root
 | id = PrimitiveRoot
}}
*{{cita web
 | last = Holt
 | title = Quadratic residues and primitive roots
 | publisher = Michigan Tech
 | department = Mathematics
 | url = http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/quadratic4.html
}}
* {{cita web
 | title = Primitive roots calculator
 | website = BlueTulip
 | url = http://www.bluetulip.org/programs/primitive.html
}}


{{control de autoridades}}
[[Categoría:Teoría de números]]
[[Categoría:Wikipedia:Páxinas con traducións non revisadas]]