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 ${\displaystyle (\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]

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

$${\displaystyle {\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.

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 ${\displaystyle (\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 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ é cíclico se e só se n é igual a 2, 4, p^k ou 2p^k onde p^k é un potencia dun número primo impar.^[6][2][7] Cando (e só cando) este grupo ${\displaystyle (\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 Xm
− 1 no anel ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$, ou simplemente un elemento primitivo de ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$.

Cando ${\displaystyle (\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 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ cíclico), a orde de ${\displaystyle (\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.

Por exemplo, se n = 14 entón os elementos de ${\displaystyle (\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, 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 n = 15. Os elementos de ${\displaystyle (\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, 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, λ(15) = 4, onde λ é a función de Carmichael. (secuencia A002322 na OEIS)

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

${\displaystyle 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 ${\displaystyle n}$ con ${\displaystyle \varphi (n)=\lambda (n),}$ (secuencia A033948 na OEIS).

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

${\displaystyle n}$	raíces primitivas módulo ${\displaystyle n}$	orde ${\displaystyle \varphi (n),}$ (OEIS: A000010)	expoñente ${\displaystyle \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

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 é ${\displaystyle 2^{6}\cdot 3^{4}\cdot 7\cdot 11^{2}\cdot 13\cdot 17=970377408\equiv 1{\pmod {31}}}$, e a súa suma é ${\displaystyle 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.

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 ${\displaystyle \varphi (n)}$ (a orde de ${\displaystyle (\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 é ${\displaystyle \varphi (n)=\lambda (n).}$ Podemos usalo para probar un candidato m para ver se é primitivo.

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

${\displaystyle 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]

${\displaystyle \varphi \left(\varphi (n)\right)}$

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

Para n primo, isto é igual a ${\displaystyle \varphi (n-1)}$, e posto que ${\displaystyle 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 2p^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.

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

• Caracter de Dirichlet
• Teorema de Wilson
• Residuo cadrático
• Raíz da unidade módulo n
• Conxectura de Artin sobre raíces primitivas

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