1.21: Clases de Residuos y los Integrados Modelo m
- Page ID
- 117405
Dejemos\(m>0\) que se den. Para cada entero\(a\) definimos\[\label{eq: [a] defn 1} [a]=\{x:x\equiv a\pmod m\}.\]
En otras palabras,\([a]\) es el conjunto de todos los enteros que son congruentes al\(a\) módulo\(m\). Llamamos a\([a]\) la clase de residuo de\(a\) módulo\(m\). Algunas personas llaman a\([a]\) la clase de congruencia o clase de equivalencia de\(a\) módulo\(m\).
Si\(m=3\) y\(a=7\), vemos\[\begin{aligned} \left[7\right] &= \{x:x \equiv 7 \pmod 3\}\\ &= \{\dots, -5, -2, 1, 4, 7, 10, 13, 16, 19, \dots\}. \end{aligned}\] Keeping\(m=3\), también vemos que\[\begin{aligned} \left[0\right] &= \{x:x \equiv 0 \pmod 3\}\\ &= \{\dots, -9, -6, -3, 0, 3, 6, 9, \dots\};\\[6pt] [1] &= \{x:x \equiv 1 \pmod 3\}\\ &= \{\dots, -8, -5, -2, 1, 4, 7, 10, \dots\};\\[6pt] [2] &= \{x:x \equiv 2 \pmod 3\}\\ &= \{\dots, -7, -4, -1, 2, 5, 8, 11, \dots\}. \end{aligned}\] Así que cada entero pertenece a una de las clases de residuo módulo 3. Tenga en cuenta también que\([7]=[1]\), ya\([7]\) y\([1]\) son ambos conjuntos que contienen exactamente los mismos elementos; pensar\([7]\) y\([1]\) como nombres diferentes para el mismo conjunto. (Con esta perspectiva, cada clase de residuo tiene infinitamente muchos nombres.)
Para\(m>0\) y cualquier entero\(a\) que tengamos\[\label{eq: [a] defn 2} [a]=\{mq+a\mid q\in\mathbb{Z}\}.\]
Prueba
\(x\in[a]\Leftrightarrow x\equiv a\pmod m\Leftrightarrow m\mid (x-a)\Leftrightarrow x-a=mq\)para algunos\(q\in\mathbb{Z}\Leftrightarrow x=mq+a\) para algunos\(q\in\mathbb{Z}\). Entonces la ecuación\(\eqref{eq: [a] defn 2}\) se desprende de la definición en ecuación\(\eqref{eq: [a] defn 1}\).
Tenga en cuenta que\([a]\) realmente depende\(m\) y sería más preciso escribir\([a]_m\) en lugar de\([a]\), pero esto sería demasiado engorroso. Sin embargo, debe tenerse claramente en cuenta que\([a]\) depende de algún valor entendido de\(m\).
Dos formas alternativas de escribir ecuaciones\(\eqref{eq: [a] defn 2}\) son\[[a]=\{mq+a\mid q=0,\pm 1,\pm 2,\dotsc\}\nonumber \] y\[[a]=\{\dotsc,-2m+a,-m+a,a,m+a,2m+a,\dotsc\}.\nonumber \]
Para un módulo dado\(m>0\) tenemos:\[[a]=[b]\Leftrightarrow a\equiv b\pmod m.\nonumber \]
Prueba
“\(\Rightarrow\)” Asumir\([a]=[b]\). Tenga en cuenta que ya\(a\equiv a\pmod m\) tenemos\(a\in[a]\). Ya\([a]=[b]\) que tenemos\(a\in[b]\). Por definición de\([b]\) esto da\(a\equiv b\pmod m\), según se desee.
“\(\Leftarrow\)” Asumir\(a\equiv b\pmod m\). Debemos demostrar que los conjuntos\([a]\) y\([b]\) son iguales. Para ello demostramos que cada elemento de\([a]\) está en\([b]\) y viceversa. Vamos\(x\in[a]\). Entonces\(x\equiv a\pmod m\). Ya que\(a\equiv b\pmod m\), por transitividad\(x\equiv b\pmod m\) así\(x\in[b]\). Por el contrario, si\(x\in[b]\), entonces\(x\equiv b\pmod m\). Por simetría desde\(a\equiv b\pmod m\),\(b\equiv a\pmod m\), así que de nuevo por transitividad\(x\equiv a\pmod m\) y\(x\in[a]\). Esto lo demuestra\([a]=[b]\).
Por cada uno\(a\) hay un único\(r\) tal que\[[a]=[r]\quad \mbox{and $0\le r<m$}.\nonumber \]
Prueba
Vamos\(r=a\bmod m\). Entonces por Teorema 1.17.2 (1) tenemos\(a\equiv r\pmod m\). Por definición de\(a\bmod m\) tenemos\(0\le r<m\). Ya que\(a\equiv r\pmod m\) por teorema\(\PageIndex{2}\),\([a]=[r]\). Para demostrar que eso\(r\) es único, supongamos también\([a]=[r']\) dónde\(0\le r'<m\). Por teorema\(\PageIndex{2}\) esto implica que\(a\equiv r'\pmod m\). Esto, junto con\(0\le r'<m\), implica por el Teorema 1.17.4 que\(r'=a\bmod m=r\).
Dado\(m>0\), hay exactamente\(m\) distintas clases de residuos módulo\(m\), a saber,\[[0],[1],[2],\dotsc,[m-1].\nonumber \]
Prueba
Por Teorema\(\PageIndex{3}\) sabemos que cada clase de residuo\([a]\) es igual a una de las clases de residuos:\([0],[1],\dotsc,[m-1]\). Por lo que no hay clases de residuos que no estén en esta lista. Estas clases de residuos son distintas por la parte de singularidad del Teorema\(\PageIndex{3}\), es decir, si\(0\le r_1<m\)\(0\le r_2<m\) y y\([r_1]=[r_2]\), entonces por la parte de singularidad del Teorema\(\PageIndex{3}\) debemos tener\(r_1=r_2\).
\(x\in[a]\)Se dice que cualquier elemento es representativo de la clase de residuos\([a]\).
Como se le pide mostrar en Ejercicio a\(\PageIndex{4}\) continuación, si\(x\) es un representante de\([a]\) entonces\([x]=[a]\), es decir, cualquier elemento de una clase de residuo puede ser utilizado para representarlo.
El módulo de enteros\(m\)
En adelante en este capítulo deja\(m\) ser un entero fijo que es mayor que 1.
Definimos es\[\mathbb{Z}_m=\{[a]\mid a\in\mathbb{Z}\},\nonumber \] decir,\(\mathbb{Z}_m\) es el conjunto de todas las clases de residuos módulo\(m\). Llamamos\(\mathbb{Z}_m\) al anillo de enteros módulo\(m\). En el siguiente capítulo mostraremos cómo sumar y multiplicar las clases de residuos. Esto\(\mathbb{Z}_m\) se convierte en un anillo. (Véase el Apéndice C para la definición de anillo.) A menudo soltamos “el anillo de” y simplemente llamamos a\(\mathbb{Z}_m\) los enteros módulo\(m\). Del Teorema\(\PageIndex{4}\)\[\mathbb{Z}_m=\{[0],[1],\dotsc,[m-1]\},\nonumber \] y como no hay dos de las clases\([0],[1],\dotsc,[m-1]\) de residuo iguales, vemos que\(\mathbb{Z}_m\) tiene exactamente\(m\) elementos. \(^{1}\)Por Ejercicio\(\PageIndex{4}\) si elegimos\[a_0\in[0],a_1\in[1],\dotsc,a_{m-1}\in[m-1]\nonumber \] entonces\[[a_0]=[0],[a_1]=[1],\dotsc,[a_{m-1}]=[m-1].\nonumber \] Así que también tenemos\[\mathbb{Z}_m=\{[a_0],[a_1],\dotsc,[a_{m-1}]\}.\nonumber \]
Si\(m=4\) tenemos, por ejemplo,\[8\in [0], 5 \in [1], -6 \in [2], 11\in [3].\nonumber \] Y de ahí:\[\mathbb{Z}_4 = \{[8],[5],[-6],[11] \}.\nonumber \]
Ahora mostramos cómo definir la adición y multiplicación de clases de residuo módulo\(m\). Es con respecto a estas operaciones binarias que\(\mathbb{Z}_m\) es un anillo (nuevamente, ver Apéndice C).
Para\([a],[b]\in\mathbb{Z}_m\) definimos\[[a]+[b]=[a+b]\nonumber \] y\[[a][b]=[ab].\nonumber \]
Para\(m=5\) tenemos\[[2]+[3]=[5],\nonumber \] y\[[2][3]=[6].\nonumber \] Note que desde\(5\equiv 0\pmod 5\) y\(6\equiv 1\pmod 5\) tenemos\([5]=[0]\) y\([6]=[1]\) así también podemos escribir\[\begin{gathered} \left[2\right]+[3]=[0] \\ [2][3]=[1].\end{gathered}\]
Dado que una clase de residuo puede tener muchos representantes, es importante verificar que las reglas dadas en Definición\(\PageIndex{4}\) no dependan de los representantes elegidos. Por ejemplo, cuando\(m=5\) sabemos eso\[[7]=[2]\text{ and }[11]=[21]\nonumber \] así deberíamos tener\[[7]+[11]=[2]+[21]\nonumber \] y\[[7][11]=[2][21].\nonumber \] En este caso podemos comprobar eso\[[7]+[11]=[18]\text{ and }[2]+[21]=[23].\nonumber \] Ahora\(23\equiv 18\pmod 5\) desde\(5\mid (23-18)\). De ahí\([18]=[23]\), como se desee. También\([7][11]=[77]\) y\([2][21]=[42]\). Entonces\(77-42=35\) y\(5\mid 35\) así\(77\equiv 42\pmod 5\) y por lo tanto\([77]=[42]\), según se desee.
Para cualquier módulo\(m>0\) si\([a]=[b]\) y\([c]=[d]\) luego\[[a]+[c]=[b]+[d]\nonumber \] y\[[a][c]=[b][d].\nonumber \]
Prueba
Ver Ejercicio\(\PageIndex{8}\) a continuación.
Al realizar la suma y multiplicación en el\(\mathbb{Z}_m\) uso de las reglas en Definición\(\PageIndex{4}\), debido al Teorema\(\PageIndex{5}\), podemos en cualquier momento reemplazar\([a]\) por\([a']\) if\(a\equiv a'\pmod m\). Esto a veces facilitará los cálculos.
Tomar\(m=151\). Entonces\(150\equiv-1\pmod{151}\) y\(149\equiv-2\pmod{151}\), así\[[150][149]=[-1][-2]=[2]\nonumber \] y\[[150]+[149]=[-1]+[-2]=[-3]=[148]\nonumber \] desde entonces\(148\equiv-3\pmod{151}\).
Cuando se trabaja con\(\mathbb{Z}_m\) él suele ser útil escribir cada clase de residuo usando su nombre\([a]\), donde\(a\) está el número menos no negativo en el conjunto. Esto lo hacemos en la construcción de las siguientes tablas de suma y multiplicación para\(\mathbb{Z}_4\). Por ejemplo,\([2]\cdot[3] = [6]\), pero dado que\([6] = [2]\) y\(2\) es el miembro no negativo más pequeño de este conjunto, la tabla registra\([2]\cdot [3] = [2]\).
| \(+\) | \([0]\) | \([1]\) | \([2]\) | \([3]\) |
|---|---|---|---|---|
| \ (+\)” style="text-align:center; ">\([0]\) | \ ([0]\)” style="text-align:center; ">\([0]\) | \ ([1]\)” style="text-align:center; ">\([1]\) | \ ([2]\)” style="text-align:center; ">\([2]\) | \ ([3]\)” style="text-align:center; ">\([3]\) |
| \ (+\)” style="text-align:center; ">\([1]\) | \ ([0]\)” style="text-align:center; ">\([1]\) | \ ([1]\)” style="text-align:center; ">\([2]\) | \ ([2]\)” style="text-align:center; ">\([3]\) | \ ([3]\)” style="text-align:center; ">\([0]\) |
| \ (+\)” style="text-align:center; ">\([2]\) | \ ([0]\)” style="text-align:center; ">\([2]\) | \ ([1]\)” style="text-align:center; ">\([3]\) | \ ([2]\)” style="text-align:center; ">\([0]\) | \ ([3]\)” style="text-align:center; ">\([1]\) |
| \ (+\)” style="text-align:center; ">\([3]\) | \ ([0]\)” style="text-align:center; ">\([3]\) | \ ([1]\)” style="text-align:center; ">\([0]\) | \ ([2]\)” style="text-align:center; ">\([1]\) | \ ([3]\)” style="text-align:center; ">\([2]\) |
| \(\cdot\) | \([0]\) | \([1]\) | \([2]\) | \([3]\) |
|---|---|---|---|---|
| \ (\ cdot\)” style="text-align:center; ">\([0]\) | \ ([0]\)” style="text-align:center; ">\([0]\) | \ ([1]\)” style="text-align:center; ">\([0]\) | \ ([2]\)” style="text-align:center; ">\([0]\) | \ ([3]\)” style="text-align:center; ">\([0]\) |
| \ (\ cdot\)” style="text-align:center; ">\([1]\) | \ ([0]\)” style="text-align:center; ">\([0]\) | \ ([1]\)” style="text-align:center; ">\([1]\) | \ ([2]\)” style="text-align:center; ">\([2]\) | \ ([3]\)” style="text-align:center; ">\([3]\) |
| \ (\ cdot\)” style="text-align:center; ">\([2]\) | \ ([0]\)” style="text-align:center; ">\([0]\) | \ ([1]\)” style="text-align:center; ">\([2]\) | \ ([2]\)” style="text-align:center; ">\([0]\) | \ ([3]\)” style="text-align:center; ">\([2]\) |
| \ (\ cdot\)” style="text-align:center; ">\([3]\) | \ ([0]\)” style="text-align:center; ">\([0]\) | \ ([1]\)” style="text-align:center; ">\([3]\) | \ ([2]\)” style="text-align:center; ">\([2]\) | \ ([3]\)” style="text-align:center; ">\([1]\) |
Recordemos que por Teorema 1.17.2 (1) tenemos para todos\(a\) y\(m>0\)\[a\equiv a\bmod m\pmod m.\nonumber \] Así que usando clases de residuo módulo\(m\) esto da\[[a]=[a\bmod m].\nonumber \]
Por lo tanto,\[\boxed{\begin{array}{c}[a]+[b]=[(a+b)\bmod m] \\ [a][b]=[(ab)\bmod m]\end{array}}\nonumber\]
Entonces si\(a\) y\(b\) están en el conjunto\(\{0,1,\dotsc,m-1\}\), estas ecuaciones nos dan una manera de obtener representaciones de la suma y producto de\([a]\) y\([b]\) usando “nombres” (representantes) también en\(\{0,1,\dotsc,m-1\}\). Esto lleva a una forma alternativa de definir\(\mathbb{Z}_m\) y sumar y multiplicar en\(\mathbb{Z}_m\). Usaremos notación ligeramente diferente.
Para\(m>0\) definir\[Z_m=\{0,1,2,\dotsc,m-1\}\nonumber \] y para\(a,b\in Z_m\)\[\begin{aligned} a+b &=(a+b)\bmod m \\ ab &=(ab)\bmod m.\end{aligned}\] donde la suma y multiplicación dentro de los paréntesis son la suma habitual y multiplicación de enteros; lo nuevo en nuestra redefinición es la práctica de reducir siempre el resultado módulo \(m\).
El conjunto\(Z_m\) con adición y multiplicación como se define es isomórfico a\(\mathbb{Z}_m\) con adición y multiplicación dadas por Definición\(\PageIndex{4}\). (Los estudiantes que tomen un curso de álgebra abstracta elemental aprenderán una definición rigurosa del término isomórfico. Por ahora, tomamos “isomórfico” para significar “tiene la misma forma”.) Las tablas de suma y multiplicación para\(Z_4\) están aquí:
| \(+\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|---|---|---|---|
| \ (+\)” style="text-align:center; ">\(0\) | \ (0\)” style="text-align:center; ">\(0\) | \ (1\)” style="text-align:center; ">\(1\) | \ (2\)” style="text-align:center; ">\(2\) | \ (3\)” style="text-align:center; ">\(3\) |
| \ (+\)” style="text-align:center; ">\(1\) | \ (0\)” style="text-align:center; ">\(1\) | \ (1\)” style="text-align:center; ">\(2\) | \ (2\)” style="text-align:center; ">\(3\) | \ (3\)” style="text-align:center; ">\(0\) |
| \ (+\)” style="text-align:center; ">\(2\) | \ (0\)” style="text-align:center; ">\(2\) | \ (1\)” style="text-align:center; ">\(3\) | \ (2\)” style="text-align:center; ">\(0\) | \ (3\)” style="text-align:center; ">\(1\) |
| \ (+\)” style="text-align:center; ">\(3\) | \ (0\)” style="text-align:center; ">\(3\) | \ (1\)” style="text-align:center; ">\(0\) | \ (2\)” style="text-align:center; ">\(1\) | \ (3\)” style="text-align:center; ">\(2\) |
| \(0\) | \(1\) | \(2\) | \(3\) | |
|---|---|---|---|---|
| \(0\) | \ (0\)” style="text-align:center; ">\(0\) | \ (1\)” style="text-align:center; ">\(0\) | \ (2\)” style="text-align:center; ">\(0\) | \ (3\)” style="text-align:center; ">\(0\) |
| \(1\) | \ (0\)” style="text-align:center; ">\(0\) | \ (1\)” style="text-align:center; ">\(1\) | \ (2\)” style="text-align:center; ">\(2\) | \ (3\)” style="text-align:center; ">\(3\) |
| \(2\) | \ (0\)” style="text-align:center; ">\(0\) | \ (1\)” style="text-align:center; ">\(2\) | \ (2\)” style="text-align:center; ">\(0\) | \ (3\)” style="text-align:center; ">\(2\) |
| \(3\) | \ (0\)” style="text-align:center; ">\(0\) | \ (1\)” style="text-align:center; ">\(3\) | \ (2\)” style="text-align:center; ">\(2\) | \ (3\)” style="text-align:center; ">\(1\) |
Vamos a resolver la congruencia\[272x\equiv 901\pmod 9.\nonumber \] Usando clases de residuo módulo\(9\), esta congruencia es equivalente a la\[[272x]=[901],\nonumber \] que es equivalente a la\[[272][x]=[901],\nonumber \] que es equivalente a\[[2][x]=[1].\nonumber \] Ahora sabemos\([x]\in\{[0],[1],\dotsc,[8]\}\) así por ensayo y error vemos que\(x=5\) es una ; en realidad, cada entero en la clase de residuo\([5]\) es una solución.
Ejercicios
Mostrar que si\(m=2\) entonces\([1]\) es el conjunto de todos los enteros impares y\([0]\) es el conjunto de todos los enteros pares. Demuestre también eso\(\mathbb{Z} = [0] \cup [1]\) y\([0] \cap [1] = \emptyset\).
Mostrar que si\(m=3\), entonces\([0]\) es el conjunto de enteros divisible por\(3\),\([1]\) es el conjunto de enteros cuyo resto cuando se divide por\(3\) es\(1\), y\([2]\) es el conjunto de enteros cuyo resto cuando se divide por\(3\) es\(2\). Demuestre también eso\(\mathbb{Z} = [0] \cup [1] \cup [2]\) y\([0] \cap [1] = [0] \cap [2] = [1] \cap [2] =\emptyset\).
Dado el módulo\(m>0\) muestran eso\([a]=[a+m]\) y\([a]=[a-m]\) para todos\(a\).
Para cualquiera\(m>0\), demuéstralo si\(x\in[a]\) entonces\([a]=[x]\).
Para cualquiera\(m>0\), demuéstralo si\([a]\cap[b]\ne\emptyset\) entonces\([a]=[b]\).
Para cualquiera\(m>0\), demuéstralo si\([a]\ne[b]\) entonces\([a]\cap[b]=\emptyset\).
Vamos\(m=2\). Demuestre eso\[[0]=[2]=[4]=[32]=[-2]=[-32]\nonumber \] y\[[1]=[3]=[-3]=[31]=[-31].\nonumber \]
Construir tablas de suma y multiplicación para\(Z_5\).
Sin hacerlo, diga cómo obtener tablas de suma y multiplicación para\(\mathbb{Z}_5\) a partir del trabajo en Ejercicio\(\PageIndex{9}\).
- Si\(p\) es un prime,\(x^2 \equiv 1 \pmod p\) demuéstralo si y solo si\(x \equiv -1 \pmod p\) o\(x \equiv 1 \pmod p\). (Pista: como parte de tu respuesta, explica por qué\(x^2 \equiv 1 \pmod p\) implica eso\(p | (x+1)(x-1)\) y aplica el Lema de Euclides (Lema 1.11.2).
- Concluir que, módulo a prime\(p\), la congruencia\([x]^2 = [1]\) tiene soluciones\([x]=[1]\) y\([x] = [-1]\).
- Encuentre un ejemplo de un módulo\(m\) y una clase de residuo\([a]\) tal que\([a]^2 = [1]\) pero\([a]\neq [1]\) y\([a]\neq [-1]\) en\(\mathbb{Z}_m\).
Resolver la congruencia\(544x \equiv 863 \pmod 7\).
Notas al pie
[1] Cada uno de esos elementos, como\([0]\) o\([1]\), es en sí mismo un conjunto con infinitamente muchos elementos, pero a menudo ignoraremos esto. Los\(m\) sets\([0],\: [1],\cdots , [m- 1]\) en\(\mathbb{Z}_m\) son sus\(m\) elementos.