5.1: El orden de los enteros y las raíces primitivas

En esta sección, estudiamos el orden de un módulo entero\(n\), donde\(n\) es positivo. También definimos raíces primitivas y resultados relacionados. El teorema de Euler en el Capítulo 4 establece que si un entero positivo\(a\) es relativamente primo a\(n\), entonces\(a^{\phi(n)}\equiv 1 (mod \ n)\). Así, por el principio de ordenamiento de pozos, hay un número entero menos positivo\(x\) que satisface esta congruencia\(a^{x}\equiv 1 (mod \ n)\).

Vamos\((a,b)=1\). El entero positivo más pequeño\(x\) tal que\(a^{x} \equiv 1(mod \ b)\) se llama el orden de\(a\) módulo\(b\). Denotamos el orden de\(a\) módulo\(b\) por\(ord_ba\).

\(ord_72=3\)desde\(2^3\equiv 1(mod \ 7)\) mientras\(2^1\equiv 2(mod \ 7)\) y\(2^2\equiv 4(mod \ 7)\).

Para encontrar todos los enteros\(x\) tales que\(a^x\equiv 1(mod \ b)\), necesitamos el siguiente teorema.

Si\((a,b)=1\) con\(b>0\), entonces el entero positivo\(x\) es una solución de la congruencia\(a^x\equiv 1(mod \ b)\) si y solo si\(ord_ba\mid x\).

Teniendo\(ord_ba\mid x\), entonces tenemos eso\(x=k.ord_ba\) para algún entero positivo\(k\). Así\[a^x=a^{kord_ba}=(a^{ord_ba})^k\equiv 1(mod \ b).\] Ahora si\(a^x\equiv 1(mod \ b)\), usamos el algoritmo de división para escribir\[x=q ord_ba+r, \ \ \ 0\leq r<ord_ba.\] Así vemos que\[a^x\equiv a^{qord_ba+r}\equiv (a^{ord_ba})^qa^r\equiv a^r (mod \ b).\] Ahora desde\(a^x\equiv 1(mod \ b)\), tenemos\(a^r\equiv 1(mod \ b)\). Ya que\(ord_ba\), obtenemos\(r=0\). Así\(x=q.ord_ba\) y por lo tanto\(ord_ba\mid x\).

Desde\(ord_72=3\), entonces\(2^{15}\equiv 1(mod \ 7)\) mientras 10 no es una solución para\(2^x\equiv 1 (mod \ 7)\).

Si\((a,b)=1\) con\(b>0\), entonces\[a^i\equiv a^j(mod \ b)\] donde\(i\) y\(j\) son enteros no negativos, si y solo si\[i\equiv j(mod \ ord_ba)\]

Supongamos que\[i\equiv j(mod \ ord_ba)\ \ \mbox{and}\ \ 0\leq j\leq i.\] Entonces tenemos\(i-j=k.ord_ba\), donde\(k\) está un entero positivo. De ahí\[a^i=a^{j+k.ord_ba}=a^j(a^{ord_ba})^k\equiv a^j (mod \ b).\] Asumir ahora que\(a^i\equiv a^j(mod \ b)\) con\(i\geq j\). Así tenemos\[a^i\equiv a^ja^{i-j}\equiv a^j(mod \ b)\] Desde\((a,b)=1\), tenemos\((a^j,b)=1\) y así por Teorema 22, obtenemos\[a^{i-j}\equiv 1(mod \ b).\] Por teorema 54, obtenemos eso\(ord_ba \mid (i-j)\) y de ahí\(i\equiv j(mod \ b)\).

Introducimos ahora raíces primitivas y discutimos sus propiedades. Nos interesan los enteros cuyo orden módulo otro entero es\(\phi(b)\). En uno de los ejercicios, se pide a uno que demuestre que si\(a\) y\(b\) son relativamente primos entonces\(ord_ba \mid \phi(b)\).

Si\((r,m)=1\) con\(m>0\) y si\(ord_mr=\phi(m)\) entonces\(r\) se llama un módulo raíz primitiva\(m\).

Observe que\(\phi(7)=6\) por lo tanto no\(2\) es un módulo raíz primitivo\(7\). Mientras\(ord_73=6\) y por lo tanto\(3\) es un módulo raíz primitiva\(7\).

Si\((r,m)=1\) con\(m>0\) y si\(r\) es un módulo raíz primitiva\(n\), entonces los enteros\(\{r^1,r^2,...r^{\phi(m)}\}\) forman un módulo de conjunto de residuos reducido\(m\).

Para probar que el conjunto\(\{r^1,r^2,...r^{\phi(m)}\}\) forma un módulo de conjunto de residuos reducidos\(m\) necesitamos demostrar que cada dos de ellos son relativamente primos y que no hay dos de ellos congruentes módulo\(m\). Ya que\((r,m)=1\), se deduce que\((r^n,m)=1\) para todos los enteros positivos\(n\). De ahí que todos los poderes de\(r\) sean relativamente primos para\(m\). Para demostrar que no hay dos potencias en el conjunto anterior son módulo equivalente\(m\), supongamos que\[r^i\equiv r^j(mod \ m).\] Por Teorema 55, vemos que\[i\equiv j(mod \ ord_m\phi(m)).\] Notemos eso\(1\leq i,j\leq \phi(m)\) y por lo tanto\(i=j\).

Si\(ord_ma=t\) y si\(u\) es un entero positivo, entonces\[ord_m(a^u)=t/(t,u).\]

Deja que\[v=ord_m(a^u),\ \ w=(t,u), \ \ t=t_1w \mbox{and}\ \ u=u_1w.\] Notemos que\((t_1,u_1)=1.\)

Porque\(t_1=t/(t,u)\), queremos demostrarlo\(ord_m(a^u)=t_1\). Para ello, vamos a mostrar eso\((a^{u})^{t_1}\equiv 1(mod \ m)\) y eso si\((a^u)^v\equiv 1(mod \ m)\), entonces\(t_1\mid v\). Primero señalar que de\[(a^u)^{t_1}=(a^{u_1w})^{(t/w)}=(a^t)^{u_1}\equiv 1(mod \ m).\] ahí por el Teorema 54, tenemos\(v\mid t_1\). Ahora por otro lado, ya que eso lo\[(a^u)^v=a^{uv}\equiv 1(mod \ m),\] sabemos\(t\mid uv\). De ahí\(t_1w\mid u_1wv\) y por lo tanto\(t_1\mid u_1v\). Porque\((t_1,u_1)=1\), eso lo vemos\(t_1\mid v\). Desde\(v\mid t_1\) y\(t_1\mid v\), concluimos que\(v=t_1=t/w=t/(t,u)\).

Eso lo vemos\(ord_73^4=6/(6,4)\) desde\(ord_73=6\).

Dejar\(r\) ser un módulo raíz primitiva\(m\), donde\(m\) es un entero positivo,\(m>1\). Entonces\(r^u\) es un módulo raíz primitivo\(m\) si y solo si\((u,\phi(m))=1\).

Por el Teorema 57, vemos que\[ord_mr^u=ord_mr/(u,ord_mr)=\phi(m)/(u,\phi(m)).\] Así\(ord_mr^u=\phi(m)\) y\(r^u\) es una raíz primitiva si y sólo si\((u,\phi(m))=1\).

El corolario anterior conduce al siguiente teorema

Si el entero positivo\(m\) tiene una raíz primitiva, entonces tiene un total de raíces primitivas\(\phi(\phi(m))\) incongruentes.

Dejar\(r\) ser un módulo raíz primitiva\(m\). Por Teorema 56, vemos que\(\{r^1,r^2,...,r^{\phi(m)}\}\) forman un módulo de sistema de residuos reducidos\(n\). Por Corolario 1, se sabe que\(r^u\) es un módulo raíz primitivo\(m\) si y solo si\((u,\phi(m))=1\). Así tenemos exactamente\(\phi(\phi(m))\) tales enteros\(u\) que son relativamente primos a\(\phi(m)\) y por lo tanto hay exactamente raíces\(\phi(\phi(m))\) primitivas módulo\(m\).

Ejercicios

1. Determinar\(ord_{13}10\).
2. Determinar\(ord_{11}3.\)
3. Demostrar que 5 es una raíz primitiva de 6.
4. Demostrar que si\(\bar{a}\) es una inversa de\(a\) módulo\(n\), entonces\(ord_na=ord_n\bar{a}\).
5. Mostrar que si\(n\) es un entero positivo, y\(a\) y\(b\) son enteros relativamente primos a\(n\) tal que\((ord_na,ord_nb)=1\), entonces\(ord_n(ab)=ord_na.ord_nb\).
6. Mostrar que si\(a\) es un entero relativamente primo al entero positivo\(m\) y\(ord_ma=st\), entonces\(ord_ma^t=s\).
7. Demuestre que si\(a\) y\(n\) son relativamente primos con\(n>0\), entonces\(ord_na \mid \phi(n)\).

Colaboradores y Atribuciones

• Template:ContribRaji