Raíz primitiva módulo n

En aritmética modular, un número Modelo:Mvar é unha raíz primitiva módulo Modelo:Mvar se todo número Modelo:Mvar coprimo con Modelo:Mvar é congruente cunha potencia de Modelo:Mvar módulo Modelo:Mvar. É dicir, Modelo:Mvar é unha raíz primitiva módulo Modelo:Mvar se para cada número enteiro Modelo:Mvar coprimo con Modelo:Mvar, hai algún número enteiro Modelo:Mvar para o cal Modelo:Mvar^Modelo:Mvar ≡ Modelo:Mvar (mod Modelo:Mvar). Tal valor Modelo:Mvar chámase índice ou logaritmo discreto de Modelo:Mvar para a base Modelo:Mvar módulo Modelo:Mvar. Polo que Modelo:Mvar é unha raíz primitiva módulo Modelo:Mvar se e só se Modelo:Mvar é 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 Modelo:Nowrap. Para todos os demais valores de n o grupo multiplicativo de enteiros módulo n non é cíclico. Isto foi probado por primeira vez por Gauss.

Exemplo elemental

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

$$\begin{array}{ccccccccc}{3}^1& =& 3^0\times 3& \equiv & 1\times 3& =& 3& \equiv & 3(\mathrm{mod}7)\\ 3^2& =& 3^1\times 3& \equiv & 3\times 3& =& 9& \equiv & 2(\mathrm{mod}7)\\ 3^3& =& 3^2\times 3& \equiv & 2\times 3& =& 6& \equiv & 6(\mathrm{mod}7)\\ 3^4& =& 3^3\times 3& \equiv & 6\times 3& =& 18& \equiv & 4(\mathrm{mod}7)\\ 3^5& =& 3^4\times 3& \equiv & 4\times 3& =& 12& \equiv & 5(\mathrm{mod}7)\\ 3^6& =& 3^5\times 3& \equiv & 5\times 3& =& 15& \equiv & 1(\mathrm{mod}7)\end{array}$$

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

Definición

Se Modelo:Mvar é un enteiro positivo, os enteiros de 1 a Modelo:Nowrap que son coprimos con Modelo:Mvar (ou de forma equivalente, as clases de congruencia coprimas con Modelo:Mvar) forman un grupo, coa multiplicación módulo Modelo:Mvar como a súa operación; denótase como $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$, e chámase o grupo de unidades módulo Modelo:Mvar, ou o grupo de clases primitivas módulo Modelo:Mvar. Como se explica no artigo [[grupo multiplicativo de enteiros módulo n|grupo multiplicativo de enteiros módulo Modelo:Mvar]], este grupo multiplicativo $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ é cíclico se e só se Modelo:Mvar é igual a 2, 4, Modelo:Mvar ou 2Modelo:Mvar onde Modelo:Mvar é un potencia dun número primo impar. 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 Modelo:Mvar (ou en linguaxe máis completa raíz primitiva da unidade módulo Modelo:Mvar, resaltando o seu papel como solución fundamental do polinomio de raíces da unidade das ecuacións polinómicas XModelo:Su − 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 Modelo:Mvar non existen. Pola contra, cada compoñente primo de Modelo:Mvar ten as súas propias raíces sub-primitivas (ver Modelo:Math nos exemplos de abaixo).

Para calquera Modelo:Mvar (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 Modelo:Mvar (Modelo:Mvar) Modelo:OEIS. E entón, o teorema de Euler di que Modelo:Nowrap para todo Modelo:Mvar coprimo con Modelo:Mvar; a potencia máis baixa de Modelo:Mvar que é congruente con 1 módulo Modelo:Mvar chámase orde multiplicativa de Modelo:Mvar módulo Modelo:Mvar. En particular, para que Modelo:Mvar sexa unha raíz primitiva módulo Modelo:Mvar, Modelo:Nowrap ten que ser a potencia máis pequena de Modelo:Mvar que sexa congruente con 1 módulo Modelo:Mvar.

Exemplos

Por exemplo, se Modelo:Nowrap entón os elementos de $(\mathbb{Z}/14\mathbb{Z}{)}^{\times }$ son as clases de congruencia {1, 3, 5, 9, 11, 13}; hai Modelo:Nowrap delas. Aquí temos unha táboa das súas potencias 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 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 Modelo:Nowrap Os elementos de $(\mathbb{Z}/15\mathbb{Z}{)}^{\times }$ son as clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hai Modelo:Nowrap delas.

 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 non hai número ningún cuxa orde sexa 8, non hai raíces primitivas módulo 15. De feito, Modelo:Nowrap, onde Modelo:Mvar é a función de Carmichael. Modelo: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, ...}.

Estes son os números $n$ con $\phi (n)=\lambda (n),$ Modelo:OEIS.

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

Modelo:Tmath	raíces primitivas módulo Modelo:Tmath	orde $\phi (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 que para calquera número primo Modelo:Mvar (coa única excepción de Modelo:Nowrap o produto das súas raíces primitivas é congruente con 1 módulo Modelo:Mvar.

Tamén demostrou que para calquera número primo Modelo:Mvar, a suma das súas raíces primitivas é congruente con Modelo:Mvar( Modelo:Mvar − 1) módulo Modelo:Mvar, onde Modelo:Mvar é a función de Möbius.

Por exemplo,

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

A conxectura de Artin sobre as raíces primitivas afirma que un enteiro dado Modelo:Mvar 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 Modelo:Mvar . Modelo:Efn Modelo:Efn 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 Modelo:Mvar módulo Modelo:Mvar é igual a $\phi (n)$ (a orde de $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$), entón é unha raíz primitiva. De feito, a inversa é verdade: se Modelo:Mvar é unha raíz primitiva módulo Modelo:Mvar, entón a orde multiplicativa de Modelo:Mvar é $\phi (n)=\lambda (n).$ Podemos usalo para probar un candidato Modelo:Mvar para ver se é primitivo.

Para $n>1$ primeiro, calcular $\phi (n).$ Despois determinar os diferentes factores primos de $\phi (n)$, digamos Modelo:Mvar₁ ,... , Modelo:Mvar. Finalmente, calcular

$g^{\phi (n)/p_i}modn\text{ para }i=1,\dots ,k$

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

O número de raíces primitivas módulo Modelo:Mvar, se as hai, é igual a

$\phi (\phi (n))$

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

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

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

Se Modelo:Mvar é unha raíz primitiva módulo Modelo:Mvar, entón Modelo:Mvar é tamén unha raíz primitiva módulo todas as potencias menores de Modelo:Mvar.

Se Modelo:Mvar é unha raíz primitiva módulo Modelo:Mvar, entón Modelo:Mvar ou Modelo:Mvar + Modelo:Mvar (o que sexa impar) é unha raíz primitiva módulo 2Modelo:Mvar.

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

Véxase tamén

Bibliografía

• Modelo:Cita libro

• Modelo:Cita publicación periódica

• Modelo:Cita libro

• Modelo:Cita libro

• Modelo:Cita libro

• Modelo:Cita libro

• Modelo:Cita publicación periódica

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

• Modelo:MathWorld
• Modelo:Cita web
• Modelo:Cita web

Modelo:Control de autoridades