Órdenes y residuos cuadráticos · Definición

Raíz primitiva

teoría de números elementalórdenes y residuos cuadráticos

Antes de empezar necesitas conocer

Las raíces primitivas permiten describir todo el grupo multiplicativo de residuos con un solo generador. Aparecen en el estudio de congruencias potenciales y de residuos cuadráticos.

Definición

Una raíz primitiva módulo \(n\) es un entero \(g\) cuyo orden multiplicativo módulo \(n\) es igual a \(\varphi(n)\), de modo que sus potencias recorren todos los residuos primos con \(n\).

\[\operatorname{ord}_n(g)=\varphi(n)\]

Si \(g\) es raíz primitiva módulo \(n\), entonces \(\gcd(g,n)=1\) y las potencias \(g^0,g^1,\dots,g^{\varphi(n)-1}\) son incongruentes entre sí módulo \(n\). Por ello el grupo de unidades módulo \(n\) es cíclico cuando existe una raíz primitiva. Esta propiedad se usa para resolver congruencias de la forma \(x^k\equiv a \pmod n\) mediante logaritmos discretos.

Ejemplo guía: módulo \(7\), \(\varphi(7)=6\). Como \(3^1=3\), \(3^2=2\), \(3^3=6\), \(3^6\equiv 1\) y ningún exponente menor da 1, el orden de 3 es 6 y por tanto 3 es raíz primitiva módulo 7.

Error típico: pensar que toda unidad es raíz primitiva. Por ejemplo, 2 tiene orden 3 módulo 7, así que no genera todo el grupo, aunque sea primo con 7.

Para pensar

¿Por qué \(2\) no es raíz primitiva módulo \(7\) aunque sea primo con \(7\)?

Porque su orden módulo \(7\) es \(3\), no \(\varphi(7)=6\).

Ejercicios 10

  1. ¿Cuál es \(\varphi(9)\)?
  2. ¿Qué significa que \(g\) sea raíz primitiva módulo \(n\)?
  3. Si \(g\) es raíz primitiva módulo \(n\), ¿cuántas potencias distintas módulo \(n\) produce \(g\)?
  4. ¿Es 3 raíz primitiva módulo 7?
  5. ¿Cuál es el orden de 2 módulo 5?
  6. ¿Es 2 raíz primitiva módulo 7?
  7. ¿Para cuál de los módulos 8, 9, 7 o 5 no existe ninguna raíz primitiva?
  8. ¿Cuál de los números 1, 2 o 4 es raíz primitiva módulo \(5\)? Considera que \(\varphi(5)=4\).
  9. ¿Cuántas raíces primitivas módulo 7 existen?
  10. Demuestra con un contraejemplo que no todo entero primo con \(n\) es raíz primitiva módulo \(n\), tomando \(n=11\) y calculando el orden de 10.

Referencias

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 8
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2