En la aritmética modular , una rama de la teoría de números , un número g es una raíz primitiva módulo n n si cada número una primos entre sí a n es congruente a una potencia de g módulo n . Es decir, g es una raíz primitiva módulo n , si para cada número entero un primos entre sí a n , hay un cierto número entero k para el que g k ≡ un (mod n ). Tal valor k se llamaíndice o logaritmo discreto de un a la base g módulo n . Tenga en cuenta que g es una raíz primitiva módulo n si y solo si g es un generador del grupo multiplicativo de números enteros módulo n .
Gauss definió las raíces primitivas en el artículo 57 de las Disquisitiones Arithmeticae (1801), donde atribuyó a Euler la acuñación del término. En el artículo 56 afirmó que Lambert y Euler los conocían, pero fue el primero en demostrar rigurosamente que las raíces primitivas existen para un primo n . De hecho, la Disquisitiones contiene dos pruebas: la del artículo 54 es una prueba de existencia no constructiva , mientras que la prueba del artículo 55 es constructiva .
Ejemplo elemental
El número 3 es una raíz primitiva módulo 7 [1] porque
Aquí vemos que el período de 3 k módulo 7 es 6. Los restos del período, que son 3, 2, 6, 4, 5, 1, forman un reordenamiento de todos los restos distintos de cero módulo 7, lo que implica que 3 es de hecho un raíz primitiva módulo 7. Esto se deriva del hecho de que una secuencia ( g k módulo n ) siempre se repite después de algún valor de k , ya que módulo n produce un número finito de valores. Si g es una raíz primitiva módulo n y n es primo, entonces el período de repetición es n - 1. Curiosamente, se ha demostrado que las permutaciones creadas de esta manera (y sus cambios circulares) son matrices de Costas .
Definición
Si n es un entero positivo, los números enteros entre 0 y n - 1 que son primos entre sí a n (o de forma equivalente, las clases de congruencia primos entre sí a n ) formar un grupo , con la multiplicación modulo n como la operación; se denota por×
n, y se denomina grupo de unidades módulo n , o grupo de clases primitivas módulo n . Como se explica en el artículo grupo multiplicativo de enteros módulo n , este grupo multiplicativo (×
n) es cíclico si y solo si n es igual a 2, 4, p k o 2 p k donde p k es una potencia de un número primo impar . [2] [3] [4] Cuando (y solo cuando) este grupo×
nes cíclico, un generador de este grupo cíclico se llama raíz primitiva módulo n [5] (o en un lenguaje más completo raíz primitiva de unidad módulo n , enfatizando su papel como una solución fundamental de las raíces de las ecuaciones polinómicas unitarias Xmetro
- 1 en el ring n ), o simplemente un elemento primitivo de ×
n. Cuándo×
nes no cíclico, tales elementos primitivos mod n no existen.
Para cualquier n (sea o no×
n es cíclico), el orden de (es decir, el número de elementos en) ×
nviene dada por la función totient de Euler φ ( n ) (secuencia A000010 en la OEIS ). Y luego, el teorema de Euler dice que un φ ( n ) ≡ 1 (mod n ) para cada una primos entre sí a n ; la potencia más baja de a que es congruente con 1 módulo n se llama orden multiplicativo de un módulo n . En particular, para un para ser una raíz primitiva módulo n , φ ( n ) tiene que ser la potencia más pequeña de una que es congruente con 1 módulo n .
Ejemplos de
Por ejemplo, si n = 14 entonces los elementos de×
nson las clases de congruencia {1, 3, 5, 9, 11, 13}; hay φ (14) = 6 de ellos. Aquí hay una tabla de sus poderes módulo 14:
xx, x 2 , x 3 , ... (mod 14) 1: 1 3: 3, 9, 13, 11, 5, 1 5: 5, 11, 13, 9, 3, 1 9: 9, 11, 111:11, 9, 113: 13, 1
El orden de 1 es 1, los órdenes de 3 y 5 son 6, los órdenes de 9 y 11 son 3 y el orden de 13 es 2. Por lo tanto, 3 y 5 son las raíces primitivas módulo 14.
Para un segundo ejemplo, sea n = 15. Los elementos de×
15son las clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hay φ (15) = 8 de ellos.
xx, x 2 , x 3 , ... (mod 15) 1: 1 2: 2, 4, 8, 1 4: 4, 1 7: 7, 4, 13, 1 8: 8, 4, 2, 111:11, 113:13, 4, 7, 114: 14, 1
Dado que no hay ningún número cuyo orden sea 8, no hay raíces primitivas módulo 15. De hecho, λ (15) = 4 , donde λ es la función de Carmichael . (secuencia A002322 en la OEIS )
Tabla de raíces primitivas
Los números que tienen una raíz primitiva son
- 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, ... (secuencia A033948 en la OEIS )
Esta es la tabla de Gauss de las raíces primitivas de los Disquisitiones . A diferencia de la mayoría de los autores modernos, no siempre eligió la raíz primitiva más pequeña. En cambio, eligió 10 si es una raíz primitiva; si no es así, eligió la raíz que dé a 10 el índice más pequeño y, si hay más de uno, eligió el más pequeño de ellos. Esto no es solo para facilitar el cálculo manual, sino que se usa en el § VI donde se investigan las expansiones decimales periódicas de los números racionales.
Las filas de la tabla están etiquetadas con las potencias primas (excepto 2, 4 y 8) inferiores a 100; la segunda columna es un módulo raíz primitivo de ese número. Las columnas están etiquetadas con primos menores que 100. La entrada en la fila p , columna q es el índice de q módulo p para la raíz dada.
Por ejemplo, en la fila 11, 2 se da como la raíz primitiva, y en la columna 5 la entrada es 4. Esto significa que 2 4 = 16 ≡ 5 (mod 11).
Para el índice de un número compuesto, sume los índices de sus factores primos.
Por ejemplo, en la fila 11, el índice de 6 es la suma de los índices de 2 y 3: 2 1 + 8 = 512 ≡ 6 (mod 11) . El índice de 25 es el doble del índice 5: 2 8 = 256 ≡ 25 (mod 11) . (Por supuesto, desde 25 ≡ 3 (mod 11) , la entrada para 3 es 8).
La tabla es sencilla para los poderes primos impares. Pero las potencias de 2 (16, 32 y 64) no tienen raíces primitivas; en cambio, las potencias de 5 representan la mitad de los números impares menos que la potencia de 2, y sus negativos módulo la potencia de 2 representan la otra mitad. Todas las potencias de 5 son congruentes con 5 o 1 (módulo 8); las columnas encabezadas por números congruentes con 3 o 7 (mod 8) contienen el índice de su negativo. (Secuencia A185189 y A185268 en OEIS )
Por ejemplo, módulo 32, el índice para 7 es 2 y 5 2 = 25 ≡ −7 (mod 32), pero la entrada para 17 es 4 y 5 4 = 625 ≡ 17 (mod 32) .
norte | raíz | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 | 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 | ||||||||||||||||||||||||
dieciséis | 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 | dieciséis | 19 | 13 | 18 | 11 | ||||||||||||||||||||
27 | 2 | 1 | * | 5 | dieciséis | 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 | dieciséis | 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 | * | dieciséis | 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 | dieciséis | 36 | 32 | 60 | 38 | 49 | 69 | 13 | 20 | 34 | 53 | 17 | 43 | 47 | |||||||
89 | 30 | 72 | 87 | 18 | 7 | 4 | sesenta y cinco | 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 | sesenta y cinco | 32 | 51 | 25 | 20 | 42 | 91 | 18 | |||||
norte | raíz | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 | 89 | 97 |
La siguiente tabla enumera las raíces primitivas módulo n para n ≤ 72:
módulo de raíces primitivas | pedido ( OEIS : A000010 ) | módulo de raíces primitivas | pedido ( OEIS : 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 | dieciséis | |
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 | dieciséis | ||
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 | ||
dieciséis | 8 | 52 | 24 | ||
17 | 3, 5, 6, 7, 10, 11, 12, 14 | dieciséis | 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 | dieciséis | ||
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 | sesenta y cinco | 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 | dieciséis | 68 | 32 | ||
33 | 20 | 69 | 44 | ||
34 | 3, 5, 7, 11, 23, 27, 29, 31 | dieciséis | 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 |
La conjetura de Artin sobre las raíces primitivas estados que da un número entero de una que no es ni un cuadrado perfecto , ni -1 es una raíz primitiva módulo un número infinito de números primos .
La secuencia de raíces primitivas más pequeñas módulo n (que no es la misma que la secuencia de raíces primitivas en la tabla de Gauss) son
- 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, ... (secuencia A046145 en la OEIS )
Para primo n , son
- 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, ... (secuencia A001918 en la OEIS )
Las raíces primitivas más grandes módulo n son
- 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, ... (secuencia A046146 en la OEIS )
Para primo n , son
- 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, ... (secuencia A071894 en la OEIS )
El número de raíces primitivas módulo n son
- 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, ... (secuencia A046144 en la OEIS )
Para primo n , son
- 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, ... (secuencia A008330 en la OEIS )
El primo más pequeño> n con raíz primitiva n son
- 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, ... (secuencia A023049 en la OEIS )
El primo más pequeño (no necesariamente superior a n ) con raíz primitiva n son
- 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, ... (secuencia A056619 en la OEIS )
Hechos aritméticos
Gauss demostró [6] que para cualquier número primo p (con la única excepción de p = 3), el producto de sus raíces primitivas es congruente con 1 módulo p .
También demostró [7] que para cualquier número primo p , la suma de sus raíces primitivas es congruente con μ ( p - 1) módulo p , donde μ es la función de Möbius .
Por ejemplo,
- p = 3, μ (2) = −1. La raíz primitiva es 2.
- p = 5, μ (4) = 0. Las raíces primitivas son 2 y 3.
- p = 7, μ (6) = 1. Las raíces primitivas son 3 y 5.
- p = 31, μ (30) = −1. Las raíces primitivas son 3, 11, 12, 13, 17, 21, 22 y 24.
- Su producto 970377408 ≡ 1 (mod 31) y su suma 123 ≡ −1 (mod 31).
- 3 × 11 = 33 ≡ 2
- 12 × 13 = 156 ≡ 1
- (−14) × (−10) = 140 ≡ 16
- (−9) × (−7) = 63 ≡ 1, y 2 × 1 × 16 × 1 = 32 ≡ 1 (mod 31).
Encontrar raíces primitivas
No se conoce una fórmula general simple para calcular raíces primitivas módulo n . [a] [b] Sin embargo, existen métodos para localizar una raíz primitiva que son más rápidos que simplemente probar todos los candidatos. Si el orden multiplicativo de un número m módulo n es igual a φ ( norte ) {\ Displaystyle \ varphi (n)} (el orden de ×
n), entonces es una raíz primitiva. De hecho, lo contrario es cierto: si m es una raíz primitiva módulo n , entonces el orden multiplicativo de m es φ ( norte ) {\ Displaystyle \ varphi (n)}
. Podemos usar esto para probar un candidato m para ver si es primitivo.
Primero, calcule . Luego determine los diferentes factores primos de, digamos p 1 , ..., p k . Finalmente, calcule
utilizando un algoritmo rápido para la exponenciación modular , como la exponenciación al cuadrado . Un número m para el cual estos k resultados son todos diferentes de 1 es una raíz primitiva.
El número de raíces primitivas módulo n , si las hay, es igual a [8]
ya que, en general, un grupo cíclico con r elementos tienegeneradores. Para primo n , esto es igual a, y desde los generadores son muy comunes entre {2, ..., n −1} y, por lo tanto, es relativamente fácil encontrar uno. [9]
Si g es un módulo raíz primitivo p , entonces g también es un módulo raíz primitivo todas las potencias p k a menos que g p −1 ≡ 1 (mod p 2 ); en ese caso, g + p es. [10]
Si g es una raíz primitiva módulo p k , entonces g o g + p k (el que sea impar) es una raíz primitiva módulo 2 p k . [10]
Encontrar raíces primitivas módulo p también equivale a encontrar las raíces del ( p - 1) st polinomio ciclotómico módulo p .
Orden de magnitud de las raíces primitivas
La raíz menos primitiva g p módulo p (en el rango 1, 2, ..., p - 1) es generalmente pequeña.
Límites superiores
Burgess (1962) demostró [11] que para cada ε > 0 hay una C tal que
Grosswald (1981) demostró [11] que si, luego
Shoup (1990, 1992) demostró, [12] asumiendo la hipótesis generalizada de Riemann , que g p = O (log 6 p ).
Límites inferiores
Fridlander (1949) y Salié (1950) demostraron [11] que existe una constante positiva C tal que para un número infinito de primos g p > C log p .
Se puede demostrar [11] de una manera elemental que para cualquier entero positivo M hay infinitamente muchos números primos tal que M < g p < p - M .
Aplicaciones
A raíz primitiva módulo n se utiliza a menudo en la criptografía , incluyendo el intercambio de claves Diffie-Hellman esquema. Los difusores de sonido se han basado en conceptos teóricos de números como raíces primitivas y residuos cuadráticos . [13] [14]
Ver también
- La conjetura de Artin sobre las raíces primitivas
- Personaje de Dirichlet
- Prime reptend completo
- Generalización de Gauss del teorema de Wilson
- Orden multiplicativo
- Residuo cuadrático
- Raíz de unidad módulo n
Notas al pie
- ^ "Uno de los problemas sin resolver más importantes en la teoría de campos finitos es diseñar un algoritmo rápido para construir raíces primitivas. Von zur Gathen & Shparlinski 1998 , pp. 15-24
- ^ "No existe una fórmula conveniente para calcular [la raíz menos primitiva]". Robbins 2006 , pág. 159
Referencias
- ^ Stromquist, Walter. "¿Qué son las raíces primitivas?" . Matemáticas. Bryn Mawr College. Archivado desde el original el 3 de julio de 2017 . Consultado el 3 de julio de 2017 .
- ^ Weisstein, Eric W. "Modulo Multiplication Group" . MathWorld .
- ^ Raíz primitiva , Enciclopedia de las matemáticas .
- ^ Vinogradov 2003 , págs. 105-121, § VI Raíces e índices primitivos.
- ^ Vinogradov 2003 , p. 106.
- ^ Gauss y Clarke 1986 , arts. 80 .
- ^ Gauss y Clarke 1986 , arte 81 .
- ^ (secuencia A010554 en la OEIS )
- ^ Knuth, Donald E. (1998). Algoritmos seminuméricos . El arte de la programación informática. 2 (3ª ed.). Addison – Wesley. sección 4.5.4, página 391.
- ^ a b Cohen, Henri (1993). Un curso de teoría de números algebraicos computacionales . Berlín: Springer . pag. 26. ISBN 978-3-540-55640-4.
- ^ a b c d Ribenboim, Paulo (1996). El nuevo libro de registros de números primos . Nueva York, NY: Springer . pag. 24. ISBN 978-0-387-94457-9.
- ^ Bach y Shallit 1996 , p. 254.
- ^ Walker, R. (1990). El diseño y aplicación de elementos difusores acústicos modulares (PDF) . Departamento de Investigación de la BBC (Informe). British Broadcasting Corporation . Consultado el 25 de marzo de 2019 .
- ^ Feldman, Eliot (julio de 1995). "Una rejilla de reflexión que anula la reflexión especular: un cono de silencio". J. Acoust. Soc. Am . 98 (1): 623–634. Código bibliográfico : 1995ASAJ ... 98..623F . doi : 10.1121 / 1.413656 .
Error de cita: una referencia definida por lista denominada "Carella-2015" no se utiliza en el contenido (consulte la página de ayuda ).
Fuentes
- Bach, Eric; Shallit, Jeffrey (1996). Algoritmos eficientes . Teoría algorítmica de números. Yo . Cambridge, MA: The MIT Press . ISBN 978-0-262-02405-1.
- Carella, NA (2015). "Raíces primitivas primitivas mínimas". Revista Internacional de Matemáticas e Informática . 10 (2): 185-194. arXiv : 1709.01172 .
The Disquisitiones Arithmeticae se ha traducido del latín ciceroniano de Gauss al inglés y al alemán. La edición alemana incluye todos sus artículos sobre teoría de números: todas las pruebas de reciprocidad cuadrática, la determinación del signo de la suma de Gauss, las investigaciones sobre la reciprocidad bicuadrática y notas inéditas.
- Gauss, Carl Friedrich (1986) [1801]. Disquisitiones Arithmeticae . Traducido por Clarke, Arthur A. (2ª, ed. Corregida). Nueva York, NY: Springer . ISBN 978-0-387-96254-2.
- Gauss, Carl Friedrich (1965) [1801]. Untersuchungen über höhere Arithmetik [ Estudios de aritmética superior ] (en alemán). Traducido por Maser, H. (2ª ed.). Nueva York, NY: Chelsea. ISBN 978-0-8284-0191-3.
- Robbins, Neville (2006). Teoría de números iniciales . Jones y Bartlett Learning. ISBN 978-0-7637-3768-9.
- Vinogradov, IM (2003). "§ VI Raíces e índices primitivos" . Elementos de la teoría de números . Mineola, NY: Publicaciones de Dover. págs. 105-121. ISBN 978-0-486-49530-9.
- von zur Gathen, Joachim ; Shparlinski, Igor (1998). "Órdenes de períodos de Gauss en campos finitos". Álgebra aplicable en Ingeniería, Comunicación y Computación . 9 (1): 15-24. CiteSeerX 10.1.1.46.5504 . doi : 10.1007 / s002000050093 . Señor 1624824 . S2CID 19232025 .
Otras lecturas
- Ore, Oystein (1988). Teoría de números y su historia . Dover. págs. 284-302 . ISBN 978-0-486-65620-5..
enlaces externos
- Weisstein, Eric W. "Raíz primitiva" . MathWorld .
- Bosquecillo. "Residuos cuadráticos y raíces primitivas" . Matemáticas. Michigan Tech.
- "Calculadora de raíces primitivas" . BlueTulip .