5.3: La existencia de raíces primitivas
- Page ID
- 114914
En esta sección, demostramos qué enteros tienen raíces primitivas. Comenzamos mostrando que cada poder de un primo impar tiene una raíz primitiva y para ello comenzamos mostrando que cada cuadrado de un primo impar tiene una raíz primitiva.
Si\(p\) es un primo impar con raíz primitiva\(r\), entonces uno puede tener cualquiera\(r\) o\(r+p\) como un módulo raíz primitiva\(p^2\).
Observe que ya que\(r\) es un módulo raíz primitiva\(p\)\(m=ord_{p^2}r\), luego\[ord_pr=\phi(p)=p-1.\] Let, luego\[r^m\equiv 1(mod \ p^2).\] Así\[r^m\equiv 1(mod \ p).\] Por Teorema 54, tenemos\[p-1\mid m.\] Por el Ejercicio 7 de la sección 6.1,\[m\mid \phi(p^2).\] también tenemos eso También,\(\phi(p^2)=p(p-1)\) y así\(m\) bien divide\(p\) o \(p-1\). Y desde\(p-1\mid m\) entonces tenemos\[m=p-1 \ \ \mbox{or} \ \ m=p(p-1).\] If\(m=p(p-1)\) y\(ord_{p^2}r=\phi(p^2)\) entonces\(r\) es un módulo raíz primitivo\(p^2\). De lo contrario, tenemos\(m=p-1\) y así\[r^{p-1}\equiv 1(mod \ p^2).\] Let\(s=r+p\). Entonces también\(s\) es un módulo raíz primitiva\(p\). De ahí que sea\(ord_{p^2}s\) igual a cualquiera\(p-1\) o\(p(p-1)\). Eso lo demostraremos\(ord_{p^2}s\neq p-1\) para que\(ord_{p^2}s=p(p-1)\). Obsérvese que\[\begin{aligned} s^{p-1}=(r+p)^{p-1}&=&r^{p-1}+(p-1)r^{p-2}p+...+p^{p-1}\\&=& r^{p-1}+(p-1)p.r^{p-2}(mod \ p^2).\end{aligned}\] De ahí\[p^2\mid s^{p-1}-(1-pr^{p-2}.\] Tenga en cuenta también que si\[p^2 \mid (s^{p-1}-1),\] entonces\[p^2\mid pr^{p-2}.\] Así tenemos\[p\mid r^{p-2}\] lo que es imposible porque\(p\nmid r\). Porque\(ord_{p^2}s\neq p-1\), podemos concluir que\[ord_{p^2}s=p(p-1)=\phi(p^2).\] Así,\(s=r+p\) es una raíz primitiva de\(p^2\).
Observe que 7 tiene 3 como raíz primitiva. \(ord_{49}3=6\)O bien\(ord_{49}3=42\). Pero desde\(3^6\not\equiv 1(mod \ 49)\). De ahí\(ord_{49}3=42\). De ahí que 3 sea una raíz primitiva de 49.
Ahora demostramos que cualquier poder de un primo impar tiene una raíz primitiva.
Dejar\(p\) ser un primo impar. Entonces cualquier poder de\(p\) es una raíz primitiva. Además, si\(r\) es un módulo raíz primitivo\(p^2\), entonces\(r\) es un módulo raíz primitivo\(p^m\) para todos los enteros positivos\(m\).
Por el Teorema 62, sabemos que cualquier primo\(p\) tiene una raíz primitiva\(r\) que también es un módulo raíz primitiva\(p^2\), así\[\label{1} p^2\nmid (r^{p-1}-1).\] demostraremos por inducción que\[\label{2} p^m\nmid (r^{p^{m-2}(p-1)}-1)\] para todos los enteros\(m\geq 2\). Una vez que probamos la congruencia anterior, mostramos que también\(r\) es un módulo raíz primitivo\(p^m\). Vamos\(n=ord_{p^m}r\). Por Teorema 54, eso lo sabemos\(n\mid \phi(p^m)\). También, eso lo sabemos\(\phi(p^m)=p^m(p-1)\). De ahí\(n\mid p^m(p-1)\). Por otro lado, porque también\[p^m\mid (r^n- 1),\] sabemos que\[p\mid (r^n-1).\] Desde\(\phi(p)=p-1\), vemos que por Teorema 54, tenemos\(n=l(p-1)\). también\(n\mid p^{m-1}(p-1)\), tenemos eso\(n=p^s(p-1)\), donde\(0 \leq s\leq m-1\). Si\(n=p^s(p-1)\) con\(s\leq m-2\), entonces\[p^k\mid r^{p^{m-2}(p-1)}-1,\] que es una contradicción. De ahí\[ord_{p^m}r=\phi(p^m).\]
Demostramos ahora ([2]) por inducción. Supongamos que nuestra afirmación es cierta para todos\(m\geq 2\). Entonces\[p^m\nmid (r^{p^{m-2}(p-1)}-1).\] Porque\((r,p)=1\), eso lo vemos\((r,p^{m-1})=1\). También sabemos por el teorema de Euler que\[p^{m-1}\mid (r^{p^{m-2}(p-1)}-1).\] Así existe un entero\(k\) tal que\[r^{p^{m-2}(p-1)}=1+kp^{m-1}.\] donde\(p\nmid k\) porque\(r^{p^{m-2}(p-1)}\not\equiv 1(mod \ p^m)\). Así tenemos ahora\[\begin{aligned} r^{p^{m-1}(p-1)}&=&(1+kp^{m-1})^p\\ &\equiv&1+kp^m(mod \ p^{m+1})\end{aligned}\] Porque\(p\nmid k\), tenemos\[p^{m+1}\nmid (r^{p^{m-1}(p-1)}-1).\]
Dado que 3 es una raíz primitiva de 7, entonces 3 es una raíz primitiva\(7^k\) para todos los enteros positivos\(k\).
En el siguiente teorema, demostramos que ninguna potencia de 2, que no sea 2 o 4, tiene una raíz primitiva y eso es porque cuando\(m\) es un entero impar,\(ord_2^km\neq \phi(2^k)\) y esto es porque\(2^k\mid (a^{\phi(2^k)/2}-1)\).
Si\(m\) es un entero impar, y si\(k\geq 3\) es un entero, entonces\[m^{2^{k-2}}\equiv 1(mod \ 2^k).\]
Demostramos el resultado por inducción. Si\(m\) es un entero impar, entonces\(m=2n+1\) para algún entero\(n\). De ahí\[m^2=4n^2+4n+1=4n(n+1)+1.\] que, de ello se deduce\(8\mid (m^2-1)\).
Supongamos ahora que\[2^k\mid (m^{2^{k-2}}-1).\] Entonces hay un entero\(q\) tal que\[m^{2^{k-2}}=1+q.2^{k}.\] así cuadrando ambos lados, obtenemos\[m^{2^{k-1}}=1+q.2^{k+1}+q^22^{2k}.\] Así\[2^{k+1}\mid (m^{2^{k-1}}-1).\]
Obsérvese ahora que 2 y 4 tienen raíces primitivas 1 y 3 respectivamente.
Ahora enumeramos el conjunto de enteros que no tienen raíces primitivas.
Si no\(m\) es\(p^a\) o\(2p^a\), entonces\(m\) no tiene una raíz primitiva.
Vamos\(m=p_1^{s_1}p_2^{s_2}...p_i^{s_i}\). Si\(m\) tiene una raíz primitiva\(r\) entonces\(r\) y\(m\) son relativamente primos y\(ord_mr=\phi(m)\). También tenemos, tenemos\((r,p^s)=1\) donde\(p^s\) está de los primos en la factorización de\(m\). Por el teorema de Euler,\[p^s\mid (r^{\phi(p^s)}-1).\] ahora tenemos que dejar que lo\[L=[\phi(p_1^{s_1}), \phi(p_2^{s_2}),...,\phi(p_i^{s_i})].\] sepamos\[r^L\equiv 1(mod \ p_k^{s_k})\] para todos\(1\leq k\leq m\). Así, usando el Teorema del Resto Chino, obtenemos\[m\mid (r^L-1),\] lo que lleva a\(ord_mr=\phi(m)\leq L\). Ahora porque\[\phi(m)=\phi(p_1^{s_1})\phi(p_2^{s_2})...\phi(p_n^{s_n})\leq [\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})].\] Ahora la desigualdad anterior se mantiene sólo si\[\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})\] son relativamente primos. Observe ahora que por el Teorema 41, no\[\phi(p_1^{s_1}),\phi(p_2^{s_2}),...,\phi(p_n^{s_n})\] son relativamente primos a menos que\(m=p^s\) o\(m=2p^s\) donde\(p\) sea un primo impar y\(t\) sea cualquier entero positivo.
Ahora mostramos que todos los enteros de la forma\(m=2p^s\) tienen raíces primitivas.
Considera un primo\(p\neq 2\) y let\(s\) es un entero positivo, entonces\(2p^s\) tiene una raíz primitiva. De hecho, si\(r\) es un módulo raíz primitiva impar\(p^s\), entonces también es un módulo raíz primitivo\(2p^s\) pero si\(r\) es par,\(r+p^s\) es un módulo raíz primitivo\(2p^s\).
Si\(r\) es un módulo raíz primitiva\(p^s\), entonces\[p^s\mid (r^{\phi(p^s)}-1)\] y ningún exponente positivo menor que\(\phi(p^s)\) tiene esta propiedad. Tenga en cuenta también\[\phi(2p^s)=\phi(p^s),\] que para que\[p^s\mid (r^{\phi(2p^s)}-1).\]
Si\(r\) es impar, entonces\[2\mid (r^{\phi(2p^s)}-1).\] Así por Teorema 56, obtenemos\[2p^s\mid (r^{\phi(2p^s)}-1).\] Es importante señalar que ninguna potencia menor de\(r\) es congruente a 1 módulo\(2p^s\). Este poder también sería congruente con 1 módulo\(p^s\) contradiciendo que\(r\) es una raíz primitiva de\(p^s\). De ello se deduce que\(r\) es un módulo raíz primitivo\(2p^s\).
Mientras que, si\(r\) es par, entonces\(r+p^s\) es impar. De ahí\[2\mid ((r+p^s)^{\phi(2p^s)}-1).\]
Porque\(p^s\mid (r+p^s-r)\), vemos eso\[p^s\mid ((r+p^s)^{\phi(2p^s)}-1).\] Como resultado, vemos eso\(2p^s\mid ((r+p^s)^{\phi(2p^s)}-1)\) y ya que para no menor potencia de\(r+p^s\) es congruente a 1 módulo\(2p^s\), vemos que\(r+p^s\) es un módulo raíz primitivo\(2p^s\).
Como resultado, por el Teorema 63, Teorema 65 y Teorema 66, vemos que
El entero positivo\(m\) tiene una raíz primitiva si y solo si\(n=2,4, p^s\) o\(2p^s\)
para prime\(p\neq 2\) y\(s\) es un entero positivo.
Ejercicios
- ¿Cuál de los siguientes enteros 4, 12, 28, 36, 125 tiene una raíz primitiva?
- Encuentra una raíz primitiva de 4, 25, 18.
- Encuentra todas las raíces primitivas módulo 22.
- Mostrar que hay el mismo número de raíces primitivas módulo\(2p ^s\) que hay módulo\(p^s\), donde\(p\) es un primo impar y\(s\) es un entero positivo.
- Encuentra todas las raíces primitivas módulo 25.
- Mostrar que el entero\(n\) tiene una raíz primitiva si y sólo si las únicas soluciones de la congruencia\(x^2\equiv 1(mod n)\) son\(x\equiv \pm1 (mod \ n)\).