raizprim

Rafael Parra Machío

RAÍCES PRIMITIVAS, INDICES MODULARES Y SISTEMAS

10. RAICES PRIMITIVAS, INDICES MODULARES Y SISTEMAS
10.1 Raíces primitivas
1.1 Raíz primitiva: definición.
Dados ݉, ݊ tales que ݉ܿ݀ሺ݉, ݊ሻ = 1, el menor ݃ tal que ݊ ௚ ≡ 1ሺ݉ó݀. ݉ሻ se denomina gaussiano de ݊ respecto de ݉. Si ݉ es un primo y ݊ es un número cualquiera tal que m F n, y el
gaussiano de ݊ es m−1, entonces se dice quen es una raíz primitiva de ݉.
El número de raíces primitivas de m viene determinada por la función ϕ(m − 1) , siendo

(m − 1) = m1a1 ⋅ m2a 2 ⋅ ... ⋅ mr ar . Si en α se cumple que α ( p −1)/ p 1 T 1(mód . p), con p primo, y
también en α( p−1)/ pr T 1(mód.p) entonces, α es la raíz primitiva de p. En efecto. Notemos que
si p F n, entonces np−1 ª 1(mód.p), con lo que, si el gaussiano de ݊ no es p−1,deberá ser un
divisor de p−1. Pero en este caso, si el gaussiano se descompone en factores primos como

p

β1
1

…p

βr
r

donde alguno de los βi puede ser cero, y suponiendo que β j < α j , tenemos que

( p−1)/ β j

α
ª 1(mód.p) luego, el número de raíces primitivas de ‫ ݌‬viene determinado por ϕ(p −1).
Dada ݊ una raíz primitiva de ‫݌‬, se tiene que los valores n0 , n1 ,…, np−2 dan restosdistintos dos a
dos (mód.p). Dado a , si existe β ∈ {0,…, p − 2} tal que nβ ª a(mód.p), entonces se dice que β
es índice modular de ܽ en base ݊, y se denota como β = In (a) = Indna.
No todos los módulos poseen raíces primitivas. Los casos en que existen raíces primitivas respecto de un módulo m , con m> 1 son, m = {2,4, pα ,2pα } , en donde p es primo y α ≥ 1.

1.2 Calcular la raíz primitiva de 11.
Paracalcular la raíz primitiva de 11, empezaremos por descomponer en factores primos
ϕ ( p − 1) = 10 = 2 ⋅ 5, 10 2 = 5 y 10 5 = 2. Por consiguiente, para que un número α no sea divisible por 11, sea raíz primitiva respecto del módulo 11, es necesario y suficiente que este
número α no satisfaga a ninguna de las congruencias α 2 ª 1(mód .11) o α 5 ª 1(mód .11). Para

α = 2 , 2(10/2) = 25 ª −1(mód.11) noes congruente con 11, y para 2(10/5) = 22 ª 4(mód .11),
tampoco es congruente con 11, luego 2 es la raíz primitiva de 11.

1.3 Calcular la raíz primitiva de 13.
Sea p = 13. ϕ ( p − 1) = 12 = 22 ⋅ 3 = 2 ⋅ 6, 12 2 = 6 y 12 6 = 2, que para α = 2 , tenemos

2(12/ 2) = 26 ≡ −1(mód .13) y 2(12/6) = 22 ≡ 4(mód .13). Ninguna de las dos congruencias satisface,
ni a α 2 ≡ 1(mód .13) ni a α 6 ≡ 1(mód .13)luego, la raíz primitiva de 13 es 2.

1.4 Calcular la raíz primitiva de 17.
Tenemos que p = 17 y ϕ ( p − 1) = 16 = 24 = 2 ⋅ 8, donde 16 2 = 8 y 16 8 = 2. Para α = 3,

3(16/2) = 38 ª 16 ª −1(mód.17)

y

para

3(16/8) = 32 ª 9(mód .17),

que

no

satisfacen

a

α ,α ª 1(mód .17) por tanto, la raíz primitiva de 17 es 3.
2

8

1

Rafael Parra Machío

RAÍCES PRIMITIVAS, INDICES MODULARES Y SISTEMAS

1.5Calcular la raíz primitiva de 23.
Tenemos que p = 23 y ϕ ( p − 1) = 22 = 2 ⋅ 11, donde 22 2 = 11 y 22 11 = 2. Para α = 3 ,

3( 22 / 2 ) = 311 ≡ 1(mód .23) que es congruente y 3( 22 / 11) = 3 2 ≡ 9(mód .23) que no es congruente con 1 módulo 23 y, por tanto, 3 no es raíz primitiva de 23. Probamos con α = 5. Tenemos que, 5 ( 22 / 2 ) = 511 ≡ 22(mód .23) y 5 ( 22 / 11) = 5 2 ≡ 2(mód .23) , ambas sonincongruentes con 1 módulo 23, luego 5 es la raíz primitiva de 23.

1.6 Calcular las raíces primitivas de los enteros n < 100 .
Utilizando el programa ‫ݐܽܯ‬ℎ݁݉ܽ‫݅ݏݎ݁ݒ ܽܿ݅ݐ‬ó݊ 6.1, las raíces primitivas de los enteros comprendidos entre el 1 y 99, son,
n
0
1
2
3
4
5
6
7
8
9

0
3

1
0
2

2
1
7

3
6

4
3
3

5
2

6
5

2

7

3
3
2

3
2
7
2

3
2
2
5

5
5

8
5

9
2
2
2

3
3

3
7

7
3
3
2
2
5

3
2

2
5
25

3
3

3
5

5

3

Nota: Las casillas en blanco son números que no tienen raíz primitiva.

1.7 Demostrar la no existencia de raíces primitivas mód.2α para α s 3 .
α

Sea ‫ ݔ‬un entero impar. Si α s 3, tenemos que x ϕ (2

)/2

ª 1(mód.2α ) luego, no existen raíces
α

primitivas mód. 2α. Efectivamente, si α = 3, la ecuación x ϕ (2 )/2 ª 1(mód.2α ) establece que
x 2 ª 1(mód .23 ) para ‫ ݔ‬impar....