Congruencias y anillo de clases residuales

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.

  1. 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]$.
  2. 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).$
  3. 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$
  4. 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.$
  5. 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$
  6. 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}\}.$
  7. 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.
  8. 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$
  9. 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.
  10. 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.
  11. 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$
  12. 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$.
  13. 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.$
  14. 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$.

  15. 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$
  16. 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.
Esta entrada fue publicada en Uncategorized y etiquetada , , , , . Guarda el enlace permanente.