3.2: Sistemas de Residuos y la función Φ-función de Euler
- Page ID
- 114983
residuo de\(a\) módulo\(m\). Como resultado, vemos que cualquier entero es congruente con uno de los enteros\(0,1,2,...,m-1\) módulo m.
Un módulo de sistema de residuos completo\(m\) es un conjunto de enteros tal que cada entero es módulo congruente\(m\) con exactamente un entero del conjunto.
El módulo de sistema de residuos completo más fácil\(m\) es el conjunto de enteros\(0,1,2,...,m-1\). Cada entero es congruente con uno de estos enteros módulo\(m\).
El conjunto de enteros\(\{0,1,2,3,4\}\) forman un módulo completo de sistema de residuos\(5\). Otro módulo completo del sistema de residuos\(5\) podría ser\(6,7,8,9,10\).
Un módulo de sistema de residuos reducidos\(m\) es un conjunto de enteros\(r_i\) tales que\((r_i,m)=1\) para todos\(i\) y\(r_i \neq r_j (mod \ m)\) si\(i\neq j\).
Observe que, se\(m\) puede obtener un módulo de sistema de residuos reducido eliminando todos los elementos del conjunto completo del sistema de residuos que no son relativamente primos a\(m\).
El conjunto de enteros\(\{1,5\}\) es un módulo de sistema de residuos reducidos\(6\).
El siguiente lema ayudará a determinar un sistema de residuos completo módulo cualquier entero positivo\(m\).
LEMMA
Un conjunto de enteros\(m\) incongruentes módulo\(m\) forma un módulo completo de sistema de residuos\(m\).
Vamos a probar este lema por contradicción. Supongamos que el conjunto de\(m\) enteros no forma un módulo completo de sistema de residuos\(m\). Entonces podemos encontrar al menos un entero\(a\) que no sea congruente con ningún elemento de este conjunto. De ahí que ninguno de los elementos de este conjunto sea realmente congruente con el resto cuando\(a\) se divide por\(m\). Dividiendo así por\(m\) rendimientos a como máximo\(m-1\) restos. Por lo tanto, por el principio de encasillado, al menos dos enteros en el conjunto que tienen el mismo resto módulo\(m\). Esto es una contradicción ya que el conjunto de enteros está formado por\(m\) enteros que son incongruentes módulo\(m\).
Si\(a_1, a_2,...,a_m\) es un módulo de sistema de residuos completo\(m\), y si\(k\) es un entero positivo con\((k,m)=1\), entonces\[ka_1+b, ka_2+b,...,ka_m+b\] es otro módulo de sistema de residuos completo\(m\) para cualquier entero\(b\).
Demostremos primero que no hay dos elementos del conjunto\(\{ka_1+b, ka_2+b,...,ka_m+b\}\) congruentes módulo\(m\). Supongamos que existe\(i\) y\(j\) tal que\[ka_i+b\equiv ka_j+b(mod\ m).\] Así obtenemos eso\[ka_i\equiv ka_j(mod \ m).\] Ahora ya que\((k,m)=1\), obtenemos\[a_i\equiv a_j(mod\ m)\] Pero para\(i\neq j\),\(a_i\) es inequivalente a\(a_j\) módulo\(m\). Así\(i=j\). Ahora observe que hay enteros\(m\) inequivalentes módulo m y así por Lemma 10, el conjunto forman un módulo completo de sistema de residuos\(m\).
\(\phi\)Función de Euler
Ahora presentamos una función que cuenta el número de enteros positivos menores que un entero dado que son relativamente primos a ese entero dado. Esta función se llama Euler\(\phi\) -function. Discutiremos las propiedades de Euler\(\phi\) -función en detalle en el capítulo 5. Será suficiente para nuestros fines en este capítulo con la notación.
La\(\phi\) función Euler de un entero positivo n, denotada por\(\phi(n)\) cuenta el número de enteros positivos menores\(n\) que los que son relativamente primos a n.
Ya que 1 y 3 son los únicos dos enteros que son relativamente primos a 4 y menos de 4, entonces\(\phi(4)=2\). Además, 1,2,... ,6 son los enteros que son relativamente primos a 7 que son menores que 7, así\(\phi(7)=6\).
Ahora podemos decir que el número de elementos en un módulo de sistema de residuos reducidos\(n\) es\(\phi(n)\).
Si\(a_1,a_2,...,a_{\phi(n)}\) es un módulo de sistema de residuo reducido\(n\) y\((k,n)=1\), entonces\(ka_1,ka_2,...,ka_{\phi(n)}\) es un módulo de sistema de residuo reducido\(n\).
La prueba procede exactamente de la misma manera que la del Teorema 24.
Ejercicios
- Dar un sistema de residuos reducidos módulo 12.
- Dar un sistema de residuos completo módulo 13 que consiste únicamente en enteros impares.
- Encontrar\(\phi(8)\) y\(\phi(101)\).