5.2: Raíces Primitivas para Primes

En esta sección, mostramos que cada entero tiene una raíz primitiva. Para ello necesitamos introducir congruencia polinomial.

Definción: congruencia polinómica

Dejar\(f(x)\) ser un polinomio con coeficientes enteros. Decimos que un entero\(a\) es una raíz de\(f(x)\) módulo\(m\) if\(f(a)\equiv 0 (mod\ m)\).

Observe que\(x\equiv 3 (mod\ 11)\) es una raíz para\(f(x)=2x^2+x+1\) desde entonces\(f(3)=22\equiv 0(mod \ 11)\).

Ahora presentamos el teorema de Lagrange para primos. Este es el módulo p, el teorema fundamental del álgebra. Este teorema será una herramienta importante para demostrar que cada primo tiene una raíz primitiva.

Teorema de Lagrange

Dejar\[m(x)=b_nx^n+b_{n-1}x^{n-1}+...+b_1x+b_0\] ser un polinomio de grado\(n, n\geq 1\) con coeficientes enteros y con coeficiente principal\(b_n\) no divisible por un primo\(p\). Entonces\(m(x)\) tiene a lo sumo\(n\) distintas raíces incongruentes módulo\(p\).

Usando inducción, observe que si\(n=1\), entonces tenemos\[m(x)=b_1x+b_0 \ \ \mbox{and} \ \ p \nmid b_1.\] Una raíz de\(m(x)\) es una solución para\(b_1x+b_0(mod \ p)\). Desde\(p\nmid b_1\) entonces esta congruencia tiene exactamente una solución por el Teorema 26.

Supongamos que el teorema es cierto para polinomios de grado\(n-1\), y deja\(m(x)\) ser un polinomio de grado\(n\) con coeficientes enteros y donde el coeficiente principal no es divisible por\(p\). Supongamos ahora que\(m(x)\) tiene raíces\(n+1\) incongruentes módulo\(p\), digamos\(x_0,x_1,...,x_{n}\). Así\[m(x_k)\equiv 0(mod \ p)\] para\(0\leq k\leq n\). Así tenemos\[\begin{aligned} m(x)-m(x_0)&=&b_n(x^n-x_0^n)+b_{n-1}(x^{n-1}-x_0^{n-1})+...+b_1(x-x_0) \\ &=& b_n(x-x_0)(x^{n-1}+x^{n-2}x_0+...+xx_0^{n-2}+x_0^{n-1})\\&+& b_{n-1}(x-x_0)(x^{n-2}+x^{n-3}x_0+...+xx_0^{n-3}+x_0^{n-2})+...+b_1(x-c_0)\\&=& (x-x_0)f(x)\end{aligned}\] donde\(f(x)\) es un polinomio de grado\(n-1\) con coeficiente principal\(b_n\). Observe que desde entonces\(m(x_k)\equiv m(x_0)(mod \ p)\), tenemos\[m(x_k)-m(x_0)=(x_k-x_0)f(x_k)\equiv 0(mod \ p).\] Así\(f(x_k)\equiv 0(mod \ p)\) para todos\(1\leq k\leq n\) y así\(x_1,x_2,...,x_n\) son raíces de\(f(x)\). Esto es una contradicción ya que tenemos un polinomio de grado\(n-1\) que tiene raíces\(n\) distintas.

Ahora utilizamos el Teorema de Lagrange para probar el siguiente resultado.

Considera el primo\(p\) y deja que\(p-1=kn\) para algún número entero\(k\). Entonces\(x^n-1\) tiene raíces exactamente\(n\) incongruentes módulo\(p\).

Ya que\(p-1=kn\), tenemos\[\begin{aligned} x^{p-1}-1&=&(x^n-1)(x^{n(k-1)}+x^{n(k-2)}+...+x^n+1) \\&=&(x^n-1)f(x)\end{aligned}\] el pequeño teorema de By Fermat, sabemos que\(x^{p-1}-1\) tiene raíces\(p-1\) incongruentes módulo\(p\). Además, las raíces de\(x^{p-1}-1\) son raíces de\(f(x)\) o una raíz de\(x^n-1\). Observe que por Teorema de Lagrange, tenemos que\(f(x)\) tiene como máximo\(p-n-1\) raíces módulo\(p\). Así\(x^n-1\) tiene al menos\(n\) raíces módulo\(p\). Pero nuevamente por el Teorema de Lagrange, ya que tenemos que\(x^n-1\) tiene como máximo\(n\) raíces, así conseguimos que\(x^n-1\) tenga raíces exactamente\(n\) incongruentes módulo\(p\).

Ahora probamos un lema que nos da cuántos enteros incongruentes pueden tener un módulo de orden dado\(p\).

Dejar\(p\) ser un primo y dejar\(m\) ser un entero positivo tal que\(p-1=mk\) para algún entero\(k\). Entonces\[S(m)=|\{m:0<m<p, \ \ m \in \mathbb{Z} \}|\leq \phi(m).\]

Para cada número entero positivo\(m\) dividiendo\(p-1\),

Observe que si\(S(m)=0\), entonces\(S(m)\leq \phi(m)\). Si\(S(m)>0\), entonces hay un entero\(a\) de orden\(m\) modulo\(p\). Ya que\(ord_pa=m\), entonces\(a,a^2,...a^m\) son incongruentes módulo\(p\). También cada potencia de\(a\) es una raíz de\(x^m-1\) módulo\(p\) porque\[(a^k)^m=(a^m)^k\equiv 1(mod \ p)\] para todos los enteros positivos\(k\). Por Teorema 60, sabemos que\(x^m-1\) tiene raíces exactamente\(m\) incongruentes módulo\(p\), de manera que cada raíz es congruente con uno de estos poderes de\(a\). También sabemos por Teorema 57 que los poderes de\(a^k\) con\((k,m)=1\) tienen orden\(m\). Hay exactamente\(\phi(m)\) tales enteros con\(1\leq k \leq m\) y por lo tanto si hay un elemento de orden\(m\) modulo\(p\), debe haber exactamente\(\phi(m)\) tales enteros positivos menores que\(p\). De ahí\(S(m)\leq \phi(m)\).

En el siguiente teorema, determinamos cuántos enteros incongruentes pueden tener un módulo de orden dado\(p\). En realidad mostramos la existencia de raíces primitivas para los números primos.

Teorema

Cada número primo tiene una raíz primitiva.

Dejar\(p\) ser un primo y dejar\(m\) ser un entero positivo tal que\(p-1=mk\) para algún entero\(k\). Dejar\(F(m)\) ser el número de enteros positivos de orden\(m\) módulo\(p\) que son menores que\(p\). El módulo\(p\) de orden de un entero no divisible por\(p\) divide\(p-1\), se deduce que\[p-1=\sum_{m\mid p-1}F(m).\] Por Teorema 42, vemos que\[p-1=\sum_{m\mid p-1}\phi(m).\] Por Lema 1,\(F(m)\leq \phi(m)\) cuando\(m\mid (p-1)\). Junto con\[\sum_{m\mid p-1}F(m)=\sum_{m\mid p-1}\phi(m)\] vemos eso\(F(m)=\phi(m)\) por cada divisor positivo\(m\) de\(p-1\). Así concluimos que\(F(m)=\phi(m)\). Como resultado, vemos que hay números enteros\(p-1\) incongruentes de\(p-1\) módulo de orden\(p\). Así\(p\) tiene raíces\(\phi(p-1)\) primitivas.

Ejercicios

1. Encuentra las raíces incongruentes módulo 11 de\(x^2+2\).
2. Encuentra las raíces incongruentes módulo 11 de\(x^4+x^2+1\).
3. Encuentra las raíces incongruentes módulo 13 de\(x^3+12\).
4. Encuentra el número de raíces primitivas de 13 y de 47.
5. Encuentra un conjunto completo de raíces primitivas incongruentes de 13.
6. Encuentra un conjunto completo de raíces primitivas incongruentes de 17.
7. Encuentra un conjunto completo de raíces primitivas incongruentes de 19.
8. \(r\)Sea una raíz primitiva de\(p\) con\(p\equiv 1(mod \ 4)\). Demostrar que también\(-r\) es una raíz primitiva.
9. Mostrar que si\(p\) es un primo y\(p\equiv 1(mod \ 4)\), entonces hay un entero\(x\) tal que\(x^2\equiv -1(mod \ p)\).

Colaboradores y Atribuciones

• Template:ContribRaji