Raíz primitiva módulo n

En aritmética modular, un número $g$ é unha raíz primitiva módulo $n$ se todo número $a$ coprimo con $n$ é congruente cunha potencia de $g$ módulo $n$ . É dicir, $g$ é unha raíz primitiva módulo $n$ se para cada número enteiro $a$ coprimo con $n$ , hai algún número enteiro $k$ para o cal $g$ ^$k$ ≡ $a$ (mod $n$ ). Tal valor $k$ chámase índice ou logaritmo discreto de $a$ para a base $g$ módulo $n$ . Polo que $g$ é unha raíz primitiva módulo $n$ se e só se $g$ é un xerador do grupo multiplicativo de enteiros módulo n, denotado $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ .

Existe unha raíz primitiva se e só se n é 1, 2, 4, p^k ou 2p^k, onde p é un primo impar e k > 0. Para todos os demais valores de n o grupo multiplicativo de enteiros módulo n non é cíclico.^[1]^[2]^[3] Isto foi probado por primeira vez por Gauss.^[4]

Exemplo elemental

O número 3 é unha raíz primitiva módulo 7^[5] porque

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

Aquí vemos que o período de 3^$k$ 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 $g$ é unha raíz primitiva módulo $n$ sendo $n$ primo, entón o período de repetición é $n$ − 1. As permutacións creadas deste xeito (e os seus desprazamentos circulares) demostráronse como matrices de Costas.

Definición

Se $n$ é un enteiro positivo, os enteiros de 1 a $n$ − 1 que son coprimos con $n$ (ou de forma equivalente, as clases de congruencia coprimas con $n$ ) forman un grupo, coa multiplicación módulo $n$ como a súa operación; denótase como $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ , e chámase o grupo de unidades módulo $n$ , ou o grupo de clases primitivas módulo $n$ . Como se explica no artigo grupo multiplicativo de enteiros módulo $n$ , este grupo multiplicativo $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ é cíclico se e só se $n$ é igual a 2, 4, $p k$ ou 2 $p k$ onde $p k$ é un potencia dun número primo impar.^[6]^[2]^[7] Cando (e só cando) este grupo $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ é cíclico, un xerador deste grupo cíclico chámase raíz primitiva módulo $n$ ^[8] (ou en linguaxe máis completa raíz primitiva da unidade módulo $n$ , resaltando o seu papel como solución fundamental do polinomio de raíces da unidade das ecuacións polinómicas X $m$
− 1 no anel $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ , ou simplemente un elemento primitivo de $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ .

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

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

Exemplos

Por exemplo, se $n$ = 14 entón os elementos de $(\mathbb {Z} /14\mathbb {Z} )^{\times }$ son as clases de congruencia {1, 3, 5, 9, 11, 13}; hai $φ$ (14) = 6 delas. Aquí temos unha táboa das súas potencias módulo 14:

 x     x, x², x³, ... (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 $n$ = 15. Os elementos de $(\mathbb {Z} /15\mathbb {Z} )^{\times }$ son as clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hai $φ$ (15) = 8 delas.

 x     x, x², x³, ... (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, $λ$ (15) = 4, onde $λ$ é a función de Carmichael. (secuencia A002322 na OEIS)

Táboa de raíces primitivas

Os números $n$ que teñen unha raíz primitiva son da forma

n\in \{1,2,4,p^{k},2\cdot p^{k}\;\;|\;\;2<p{\text{ primo}};\;k\in \mathbb {N} \},

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. ^[9]

Estes son os números $n$ con $\varphi (n)=\lambda (n),$ (secuencia A033948 na OEIS).

A seguinte táboa enumera as raíces primitivas módulo $n$ ata $n=31$ :

$n$	raíces primitivas módulo $n$	orde $\varphi (n),$ (OEIS: A000010)	expoñente $\lambda (n),$ (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^[10] que para calquera número primo $p$ (coa única excepción de $p$ = 3), o produto das súas raíces primitivas é congruente con 1 módulo $p$ .

Tamén demostrou ^[11] que para calquera número primo $p$ , a suma das súas raíces primitivas é congruente con $μ$ ( $p$ − 1) módulo $p$ , onde $μ$ é a función de Möbius.

Por exemplo,

$p$ = 3,	$μ$ (2) = −1.	A raíz primitiva é 2.
$p$ = 5,	$μ$ (4) = 0.	As raíces primitivas son 2 e 3.
$p$ = 7,	$μ$ (6) = 1.	As raíces primitivas son 3 e 5.
$p$ = 31,	$μ$ (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 é $2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}$ , e a súa suma é $123\equiv -1\equiv \mu (31-1){\pmod {31}}$ .

A conxectura de Artin sobre as raíces primitivas afirma que un enteiro dado $a$ que non é nin un cadrado perfecto nin -1 é unha raíz primitiva módulo infinitamente moitos primos.

Procurando raíces primitivas

Non se coñece unha fórmula xeral simple para calcular raíces primitivas módulo $n$ . ^[a] ^[b] 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 expoñente) dun número $m$ módulo $n$ é igual a $\varphi (n)$ (a orde de $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ ), entón é unha raíz primitiva. De feito, a inversa é verdade: se $m$ é unha raíz primitiva módulo $n$ , entón a orde multiplicativa de $m$ é $\varphi (n)=\lambda (n).$ Podemos usalo para probar un candidato $m$ para ver se é primitivo.

Para $n>1$ primeiro, calcular $\varphi (n).$ Despois determinar os diferentes factores primos de $\varphi (n)$ , digamos $p$ ₁ ,... , $p k$ . Finalmente, calcular

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

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

O número de raíces primitivas módulo $n$ , se as hai, é igual a ^[12]

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

xa que, en xeral, un grupo cíclico con $r$ elementos ten $\varphi (r)$ xeradores.

Para $n$ primo, isto é igual a $\varphi (n-1)$ , e posto que $n/\varphi (n-1)\in O(\log \log n)$ os xeradores son moi comúns entre {2, ..., $n$ − 1} e, polo tanto, é relativamente fácil atopar un.

Se $g$ é unha raíz primitiva módulo $p$ , entón $g$ é tamén unha raíz primitiva módulo todas as potencias $p k$ a menos que $g$ ^{$p$ −1} ≡ 1 (mod $p$ ²); nese caso temos que $g$ + $p$ si o é.

Se $g$ é unha raíz primitiva módulo $p k$ , entón $g$ é tamén unha raíz primitiva módulo todas as potencias menores de $p$ .

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

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

Notas

↑ Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
↑ ^2,0 ^2,1 "Primitive root - Encyclopedia of Mathematics". encyclopediaofmath.org. Consultado o 2024-11-05.
↑ (Vinogradov 2003, pp. 105–121, § VI PRIMITIVE ROOTS AND INDICES)
↑ (Gauss 1986, arts. 52–56, 82–891)
↑ Stromquist, Walter. "What are primitive roots?". Mathematics. Bryn Mawr College. Arquivado dende o orixinal o 2017-07-03. Consultado o 2017-07-03.
↑ Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.
↑ Vinogradov 2003, pp. 105–121, § VI Primitive roots and indices.
↑ Vinogradov 2003, p. 106.
↑ Gauss 1986.
↑ Gauss 1986
↑ Gauss 1986.
↑ (secuencia A010554 na OEIS)

↑ "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.von zur Gathen & Shparlinski 1998, pp. 15–24
↑ "Non hai unha fórmula conveniente para calcular a menor raíz primitiva." Robbins 2006, p. 159

Véxase tamén

Bibliografía

Bach, Eric; Shallit, Jeffrey (1996). Efficient Algorithms. Algorithmic Number Theory I. Cambridge, MA: The MIT Press. ISBN 978-0-262-02405-1.

Carella, N. A. (2015). "Least Prime Primitive Roots". International Journal of Mathematics and Computer Science 10 (2): 185–194. arXiv:1709.01172.

Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae. Traducido por Clarke, Arthur A. (2nd, corrected ed.). New York, NY: Springer. ISBN 978-0-387-96254-2.

Gauss, Carl Friedrich (1965) [1801]. Untersuchungen über höhere Arithmetik [Studies of Higher Arithmetic]. Traducido por Maser, H. (2nd ed.). New York, NY: Chelsea. ISBN 978-0-8284-0191-3.

Robbins, Neville (2006). Beginning Number Theory. Jones & Bartlett Learning. ISBN 978-0-7637-3768-9.

Vinogradov, I.M. (2003). "§ VI Primitive roots and indices". Elements of Number Theory. Mineola, NY: Dover Publications. pp. 105–121. ISBN 978-0-486-49530-9.

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. MR 1624824. doi:10.1007/s002000050093.

Outros artigos

Ligazóns externas

Weisstein, Eric W. "Primitive Root". MathWorld.
Holt. "Quadratic residues and primitive roots". Mathematics. Michigan Tech.
"Primitive roots calculator". BlueTulip.

[1] Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.

[:0-2] 2,0 ^2,1 "Primitive root - Encyclopedia of Mathematics". encyclopediaofmath.org. Consultado o 2024-11-05.

[Vinogradov2003.pp=105-121-3] (Vinogradov 2003, pp. 105–121, § VI PRIMITIVE ROOTS AND INDICES)

[4] (Gauss 1986, arts. 52–56, 82–891)

[5] Stromquist, Walter. "What are primitive roots?". Mathematics. Bryn Mawr College. Arquivado dende o orixinal o 2017-07-03. Consultado o 2017-07-03.

[6] Weisstein, Eric W. "Modulo Multiplication Group". MathWorld.

[Vinogradov2003.pp=105–121-7] Vinogradov 2003, pp. 105–121, § VI Primitive roots and indices.

[8] Vinogradov 2003, p. 106.

[9] Gauss 1986.

[10] Gauss 1986

[11] Gauss 1986.

[14] (secuencia A010554 na OEIS)

[12] "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.von zur Gathen & Shparlinski 1998, pp. 15–24

[13] "Non hai unha fórmula conveniente para calcular a menor raíz primitiva." Robbins 2006, p. 159

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[a]

[b]

[12]