RESUMEN. Definimos el concepto de congruencia en el conjunto de los números enteros y analizamos algunas de sus propiedades. También construimos el anillo de las clases residuales.
- Notaciones. Mientras no se diga lo contrario, las letras denotarán núumeros enteros. El máximo común divisor de los números $a_1,\ldots,a_r$ se representará por $(a_1,\ldots,a_r)$ y su mínimo común múltiplo por $[a_1,\ldots,a_r]$.
- Definición. Sean $a,b\in\mathbb{Z}$ y $m\in\mathbb{Z}_{>0}$. Decimos entonces que $a$ es congruente con $b$ módulo $m$ si a $a$ y $b$ les corresponde el mismo resto de su división euclídea por $m$. Escribimos en tal caso $a\equiv b\;(\text{mód }m).$
- Teorema. Las siguientes afirmaciones son equivalentes
$(i)$ $a\equiv b\;(\text{mód }m)$.
$(ii)$ $a$ es de la forma $a=b+km$ con $k$ entero.
$(iii)$ $m\mid (a-b)$.
Demostración
$(i)\Rightarrow (ii)$) En efecto, de $a\equiv b\;(\text{mód }m)$ se deduce $$a=k_1m+r,\quad b=k_2m+r;\quad 0\le r < m, $$ de donde $a-b=(k_1-k_2)m$. Por tanto, $a=b+km$ con $k=k_1-k_2$ entero.
$(ii)\Rightarrow (iii)$) Si $a$ es de la forma $a=b+km$ con $k$ entero, entonces $a-b=km$, con lo cual $m\mid (a-b)$.
$(iii)\Rightarrow (i)$) Si $m\mid (a-b)$ entonces $a-b=k_1m$. Por otra parte, $b=k_2m+r$ con $0\le r < m$. Deducimos $a=(k_1+k_2)m+r,\; 0\le r < m$ con lo cual $a\equiv b\;(\text{mód }m)$.$ \quad \square$ - Ejemplos.
1) $30\equiv 9\;(\text{mód }7)$ pues $7\mid (30-9)=21.$
2) $45\equiv 0\;(\text{mód }15)$ pues $15\mid (45-0)=45.$
3) $13\equiv -2\;(\text{mód }3)$ pues $3\mid (13-(-2))=15.$ - Teorema. Para todo $m\in\mathbb{Z}_{> 0}$ la relación en $\mathbb{Z}$ dada por $a\equiv b\;(\text{mód }m)$ es de equivalencia.
Demostración. Para todo $a\in\mathbb{Z}$ se verifica $m\mid (a-a)$ luego $a\equiv a \;(\text{mód }m)$. Si $a\equiv b\;(\text{mód }m)$ entonces $m\mid (a-b)$ con lo cual $m\mid (b-a)$ y por tanto $b\equiv a\;(\text{mód }m)$. Si $a\equiv b\;(\text{mód }m)$ y $b\equiv c\;(\text{mód }m)$ entonces $m\mid (a-b)$ y $m\mid (b-c)$ con lo cual $m\mid \left((a-b)+(b-c)\right)=(a-c)$ y por tanto $a\equiv c\;(\text{mód }m)$. $ \quad\square$ - Nota. La clase de equivalencia $\bar{a}$ a la que pertenece $a\in\mathbb{Z}$ es por tanto $\bar{a}=\{a+kn:k\in\mathbb{Z}\}.$
- Ejemplo. Para $m=3$, las clases de equivalencia son $$\bar{0}=\{0+3k:k\in\mathbb{Z}\}=\{\ldots,-6,-3,0,3,6,\ldots\}$$ $$\bar{1}=\{1+3k:k\in\mathbb{Z}\}=\{\ldots,-5,-2,1,4,7,\ldots\}$$ $$\bar{2}=\{2+3k:k\in\mathbb{Z}\}=\{\ldots,-4,-1,2,5,8,\ldots\}$$ y el conjunto cociente es $\mathbb{Z}/\equiv=\{\bar{0},\bar{1},\bar{2}\}.$
Veamos a continuación una serie de propiedades de las congruencias. - Teorema.
(1) $a\equiv b\;(\text{mód }m) \wedge c\equiv d \;(\text{mód }m) \Rightarrow a+c\equiv b+d\;(\text{mód }m)$, es decir las congruencias se pueden sumar término a término.
(2) $a\equiv b\;(\text{mód }m) \wedge c\equiv d \;(\text{mód }m) \Rightarrow ac\equiv bd\;(\text{mód }m)$, es decir las congruencias se pueden multiplicar término a término.
(3) Si $a\equiv b\;(\text{mód }m)$ y $n$ es entero no negativo entonces, $a^n\equiv b^n\;(\text{mód }m)$.
(4) Si $f\in \mathbb{Z}[x]$ y $a\equiv b\;(\text{mód }m)$, entonces $f(a)\equiv f(b)\;(\text{mód }m)$.
Demostración.
(1) Si $a\equiv b\;(\text{mód }m)$ y $c\equiv d \;(\text{mód }m) $, entonces $a=b+k_1m$ y $c=d+k_2m$ con lo cual, $a+c=b+d+(k_1+k_2)m$ y por tanto $a+c\equiv b+d\;(\text{mód }m)$.
(2) Si $a\equiv b\;(\text{mód }m)$ y $c\equiv d \;(\text{mód }m) $, entonces $a=b+k_1m$ y $c=d+k_2m$ con lo cual $ac=bd+(dk_1+bk_2+k_1k_2m)m$, y por tanto $ac\equiv bd\;(\text{mód }m)$.
(3) Es trivialmente cierto para $n=0$ y $n=1$. Si es cierto para $n\ge1$ entonces, $a^n\equiv b^n\;(\text{mód }m)$ y aplicando la propiedad (2), $a^{n+1}\equiv b^{n+1}\;(\text{mód }m)$.
(4) Sea $f(x)=\sum_{j=1}^dc_jx^j$. Por $(3)$ tenemos $a^j\equiv b^j\;(\text{mód }m)$ para cada $j$ y $c_ja^j\equiv c_jb^j\;(\text{mód }m)$ por $(2)$. Finalmente, y por aplicación repetida de $(1)$, obtenemos $f(a)=\sum_{j=1}^dc_ja^j\equiv \sum_{j=1}^dc_jb^j=f(b)\;(\text{mód }m)$. $\quad\square$ - Ejemplos.
1) Tenemos $23\equiv 2\;(\text{mód }7)$ y elevando al cuadrado $23^2\equiv 4\;(\text{mód }7)$. Con esto, tenemos una sencilla forma de hallar el resto de la división de $23^2$ entre $7$. Multiplicando de nuevo por $23\equiv 2\;(\text{mód }7)$ obtenemos $23^3\equiv 8\equiv 1\;(\text{mód }7)$. Como $23^3\equiv 1\;(\text{mód }7)$, elevando a $6$ ambos miembros de la congruencia anterior, obtenemos $23^{18}\equiv 1\;(\text{mód }7)$. Todo esto permite hallar restos de números grandes de forma sencilla.
2) Calculemos el resto de la división de $17^{341}$ entre $5.$ Tenemos $$17\equiv 2\;(\text{mód }5)\Rightarrow 17^2\equiv 4\equiv -1\;(\text{mód }5)\Rightarrow 17^4\equiv 1\;(\text{mód }5)$$ $$\Rightarrow (17^4)^{85}\equiv 1\;(\text{mód }5)\Rightarrow 17^{340}\equiv 1\;(\text{mód }5)\Rightarrow 17{341}\equiv 17\equiv 2\;(\text{mód }5)$$ y el resto de la división de $17^{341}$ entre $5$ es $2$.
A continuación vamos a ver qué ocurre cuando el módulo se multiplica o se divide por algún número. - Teorema.
$(i)$ $c>0$ y $a\equiv b\;(\text{mód }m)\Rightarrow ac\equiv bc\;(\text{mód }mc)$
$(ii)$ $d>0$, $d\mid m$ y $a\equiv b\;(\text{mód }m)\Rightarrow a\equiv b\;(\text{mód }d)$.
Demostración
$(i)$ Si $a\equiv b\;(\text{mód }m)$ entonces $m\mid (a-b)$ con lo cual $mc\mid (a-b)c=ac-bc$ y por tanto, $ac\equiv bc\;(\text{mód }mc)$.
$(ii)$ Si $a\equiv b\;(\text{mód }m)$ entonces $m\mid (a-b)$ y como $d\mid m$ tenemos $d\mid (a-b)$, por tanto $ a\equiv b\;(\text{mód }d)$. $\quad \square$
En general, las congruencias no se pueden dividir sin cambiar el módulo. Tenemos el siguiente resultado. - Teorema.Sea $c\ne 0$.
$(i)$ Si $ca\equiv cb\;(\text{mód }m)$, entonces $a\equiv b\;(\text{mód }m/(c,a))$.
$(ii)$ Si $ca\equiv cb\;(\text{mód }m)$ y $(c,m)=1$ entonces $a\equiv b\;(\text{mód }m)$.
Demostración
$(i)$ Sea $d=(c,m)$. Si $ca\equiv cb\;(\text{mód }m)$, entonces $m\mid c(a-b)$ y $\frac{m}{d}\mid \frac{c}{d}(a-b)$. Dado que $(a/d,c/d)=1$, tenemos $\frac{m}{d}\mid (a-b)$, es decir $a\equiv b\;(\text{mód }m/d)$.
$(ii)$ Es un caso particular de $(i)$. $\quad \square$ - Teorema. Sean $m_1,m_2,\ldots,m_r$ enteros positivos. Entonces, son equivalentes
$(i)$ $a\equiv b\;(\text{mód }m_i)$ para todo $i=1,2,\ldots,r$.
$(ii)$ $a\equiv b\;(\text{mód }[m_1,m_2,\ldots,m_r])$.
Demostración.
$(i)\Rightarrow (ii).$ Si $a\equiv b\;(\text{mód }m_i)$ para todo $i=1,2,\ldots,r$, entonces $(a-b)$ es un común múltiplo de todos los $m_i$ y por tanto $[m_1,m_2,\ldots,m_r]\mid (a-b)$ es decir, $a\equiv b\;(\text{mód }[m_1,m_2,\ldots,m_r])$.
$(ii)\Rightarrow (i).$ Si $a\equiv b\;(\text{mód }[m_1,m_2,\ldots,m_r])$ entonces, $[m_1,m_2,\ldots,m_r]\mid (a-b)$, pero para todo $i$ se verifica $m_i\mid [m_1,m_2,\ldots,m_r]$ con lo cual $ m_i\mid (a-b)$ para todo $i$ es decir, $a\equiv b\;(\text{mód }m_i)$ para todo $i$. $\quad\square$
Según el teorema 5, la relación en $\mathbb{Z}$ dada por $a\equiv b\;(\text{mód }m)$ es de equivalencia. Vamos a determinar el conjunto cociente $\mathbb{Z}/\equiv$ al que llamaremos $\mathbb{Z}_m$. A cada elemento de este conjunto cociente le llamamos clase residual módulo $m$. - Teorema. Existen exactamente $m$ clases residuales módulo $m$ a saber $$\mathbb{Z}_m=\{\bar{0},\bar{1},\bar{2},\ldots,\overline{m-1}\}.$$ Demostración. Sea $a\in\mathbb{Z}$. De acuerdo con el teorema de la división euclídea existe un único $r$ con $0\le r< m$ tal que $a\equiv r\;(\text{mód }m)$, por tanto $\bar{a}$ es igual a una de las clases $\bar{0},\bar{1},\bar{2},\ldots,\overline{m-1}$ y estas son todas distintas pues $i\not \equiv j\;(\text{mód }m)$ si $0\le i< j< r$. $\;\square$
A continuación vamos a construir de forma natural una estructura de anillo en $\mathbb{Z}_m.$ - Teorema. El conjunto $\mathbb{Z}_m$ de las clases residuales módulo $m$ tiene estructura de anillo conmutativo y unitario con las operaciones $$ \bar{a}+\bar{b}=\overline{a+b},\quad \bar{a}\bar{b}=\overline{ab}.$$ Demostración.
$(i)$ $(\mathbb{Z}_m, +)$ es grupo abeliano. La operación $+$ está bien definida. En efecto, si $\bar{a}=\bar{a_1}$ y $\bar{b}=\bar{b_1}$, por el apartado (1) del teorema 8, tenemos $\overline{a+b}=\overline{a_1+b_1}$ es decir la operación no depende del representante elegido en cada clase. Para todo $a,b,c$ enteros tenemos $$\bar{a}+(\bar{b}+\bar{c})=\bar{a}+\overline{b+c}=\overline{a+(b+c)}$$ $$=\overline{(a+b)+c}=\overline{a+b}+\bar{c}=(\bar{a}+\bar{b})+\bar{c},$$ luego la suma de clases es asociativa. También es conmutativa pues para todo $a,b$ enteros, $\bar{a}+\bar{b}=\overline{a+b}=\overline{b+a}=\bar{b}+\bar{a}$. Para todo $ a$ entero se verifica $\bar{a}+\bar{0}=\overline{a+0}=\bar{a}$, luego $\bar{0}$ es elemento neutro para la suma de clases. Si $a$ es entero, $\bar{a}+\overline{-a}=\overline{a+(-a)}=\bar{0}$, luego toda clase tiene elemento simétrico.$(ii)$ $(\mathbb{Z}/\equiv,\cdot)$ es semigrupo conmutativo y unitario. La operación $\cdot$ está bien definida. En efecto, si $\bar{a}=\bar{a_1}$ y $\bar{b}=\bar{b_1}$, por el apartado (2) del teorema 8 tenemos $\overline{ab}=\overline{a_1b_1}$ es decir la operación no depende del representante elegido en cada clase. Para todo $a,b,c$ enteros tenemos $$\bar{a}\cdot(\bar{b}\cdot\bar{c})=\bar{a}\cdot\overline{b\cdot c}=\overline{a\cdot(b\cdot c)}$$ $$=\overline{(a\cdot b)\cdot c}=\overline{a\cdot b}\cdot \bar{c}=(\bar{a}\cdot \bar{b})\cdot \bar{c},$$ luego el producto de clases es asociativo. También es conmutativo pues para todo $a,b$ enteros, $\bar{a}\cdot \bar{b}=\overline{a\cdot b}=\overline{b\cdot a}=\bar{b}\cdot \bar{a}$. Para todo $ a$ entero se verifica $\bar{a}\cdot \bar{1}=\overline{a\cdot 1}=\bar{a}$, luego $\bar{1}$ es elemento neutro para el producto de clases.
$(iii)$ El producto es distributivo respecto de la suma. Al ser la operación producto conmutativa, basta demostrar que para toda terna de clases $\bar{a},\bar{b}$ y $\bar{c}$ se verifica $\bar{a}(\bar{b}+\bar{c})=\bar{a}\bar{b}+\bar{b}\bar{c}.$ En efecto, $$\bar{a}(\bar{b}+\bar{c})=\bar{a}\overline{(b+c)}=\overline{a(b+c)}=\overline{ab+ac}=\overline{ab}+\overline{ac}=\bar{a}\bar{b}+\bar{b}\bar{c}.\qquad \square$$ Al anillo anterior se le llama anillo de clases residuales módulo $m$.
- Teorema. Sea $m>1$ entero. Entonces, $\mathbb{Z}_m$ es dominio de integridad $\Leftrightarrow$ $ m$ es primo.
Demostración.
$\Rightarrow)$ Si $m$ no fuera primo, entonces, $m=rs$ con $r,s$ enteros tales que $1 < r < m$ y $1 < s < m.$ Esto implicarìa $\bar r\cdot\bar s=\bar m=\bar 0$ siendo $\bar r\neq \bar 0$ y $\bar s\neq \bar 0.$ Existirían divisores de cero, en contradicción con la hipótesis de ser $\mathbb{Z}_m$ de integridad.
$\Leftarrow)$ Supongamos que $\mathbb{Z}_m=\{\bar{0},\;\bar{1},\;\bar{2},\;\ldots,\;\overline{m-1}\}$ tuviera divisores de cero, es decir que existieran elementos $\bar r$ y $\bar s$ de $\mathbb{Z}_m$ no nulos tales que $\bar r\cdot \bar s=\bar 0.$ Esto implicaría que $m$ divide a $rs.$ Ahora bien, dado que $r < m$ y $m$ es primo, $r$ y $m$ son primos entre sí, y al dividir $m$ a $rs$ y ser primo con $r,$ $m$ divide a $s$ (por tanto $\bar s=\bar 0$), lo cual es absurdo pues hemos supuesto $\bar s\neq\bar 0.$ $\quad\square$ - Corolario. Dado que todo dominio de integridad con un número finito de elementos es un cuerpo (ver Cuerpos $\mathbb{Z}_p$, apartado 5) concluimos que $\mathbb{Z}_m$ es un cuerpo si y sólo si $m$ es primo.
Las dudas o comentarios acerca de los contenidos de ésta web se pueden plantear en 
