7.4: Aritmética Modular

Supongamos, como de costumbre, que\(\sim\) es una relación de equivalencia sobre un conjunto\(A\). Escribir\(a \sim b\) significa que\(a\) es “equivalente” a\(b\). En este caso, es posible que queramos pensar que somos iguales a\(b\).\(a\) Pero eso no estaría bien, porque\(a\) y\(b\) son (probablemente) dos cosas distintas. Sin embargo, tenemos las siguientes clases de propiedad fundamental de equivalencia:\[a \sim b \quad \text { iff } \quad[a]=[b] .\]

Así, poniendo corchetes alrededor\(a\) y\(b\), podemos convertir la mera equivalencia en verdadera igualdad. Eso es lo que hace que las clases de equivalencia sean tan importantes. Un buen ejemplo lo proporciona congruencia modulo\(n\).

7.4A. Los enteros módulo 3.

Para cualquiera\(n \in \mathbb{Z}\), sabemos que el módulo de congruencia\(n\) es una relación de equivalencia (ver Ejercicio\(5.1.18\)). A modo de ejemplo, consideremos el caso donde\(n = 3\). Para enfatizar el hecho de que\(n = 3\), incluiremos un subíndice ₃ en la notación para una clase de equivalencia: escribimos\([k]_{3}\), en lugar de\([k]\).

Todos sabemos que cuando un entero se divide por 3, el resto debe ser 0, 1 o 2, así que Ejercicio nos\(5.1.22(1)\) dice que cada entero es congruente (módulo 3) con 0, 1 o 2. Por lo tanto,

• para cada\(k \in \mathbb{Z}\), la clase de equivalencia\([k]_{3}\) debe ser cualquiera\([0]_{3}\),\([1]_{3}\), o\([2]_{3}\). Por otro lado, es fácil comprobar que no hay dos de 0, 1 y 2 congruentes (módulo 3), por lo que
• \([0]_{3}\),\([1]_{3}\), y\([2]_{3}\) son tres clases de equivalencia distintas.

Así, vemos que hay exactamente tres clases de equivalencia, a saber,\([0]_{3}\),\([1]_{3}\), y\([2]_{3}\). El conjunto de estas clases de equivalencia se llama los enteros módulo 3. Se denota\(\mathbb{Z}_{3}\).

Notación\(7.4.1\).

La notación\([k]_{3}\) (o incluso simplemente\([k]\)) es bastante engorrosa. Por conveniencia, podemos escribir\(\bar{k}\) para la clase de equivalencia de\(k\). Por lo tanto,\[\mathbb{Z}_{3}=\{\overline{0}, \overline{1}, \overline{2}\} .\]

Definición\(7.4.2\).

Podemos hacer aritmética (sumar, restar y multiplicar) en estas clases de equivalencia, tal como lo hacemos para los enteros ordinarios. A esto se le llama aritmética módulo 3. Las reglas son:

• \(\left.[a]_{3}+[b]_{3}=[a+b]_{3} \quad \text { (or } \bar{a}+\bar{b}=\overline{a+b}\right),\)
• \(\left.[a]_{3}-[b]_{3}=[a-b]_{3} \quad \text { (or } \bar{a}-\bar{b}=\overline{a-b}\right) \text {, and }\)
• \([a]_{3} \times[b]_{3}=[a b]_{3} \quad(\text { or } \bar{a} \times \bar{b}=\overline{a b}) .\)

(En realidad, debemos escribir\(+_{3}\),\(−_{3}\), y\(\times_{3}\), para indicar que la aritmética se está haciendo módulo 3, pero normalmente no vamos a molestarnos.)

Ejemplo\(7.4.3\).

Nosotros tenemos\([1]_{3}+[2]_{3}=[1+2]_{3}=[3]_{3}\). Sin embargo, ya que\(3 \equiv 0(\bmod 3)\), tenemos\([3]_{3} = [0]_{3}\), por lo que la ecuación anterior también se puede escribir como

Solución

\([1]_{3}+[2]_{3}=[0]_{3}\). Equivalentemente,\(\overline{1}+\overline{2}=\overline{0}\).

Este es un ejemplo del siguiente principio general:\[\text { If } r \text { is the remainder when } a+b \text { is divided by } 3 \text {, then } \bar{a}+{ }_{3} \bar{b}=\bar{r} \text {. }\]

Ejemplo\(7.4.4\).

Aquí hay una tabla que muestra los resultados de adición módulo 3:

Solución

\ [\ begin {array} {c||c|c}
+_ {3} &\ overline {0} &\ overline {1} &\ overline {2}\\ hline
\ hline\ overline {0} &\ overline {0} &\ overline {1} &\ overline {1} &\ overline {2}
\\ hline\ overline {1} &\ overline {1} &\ overline {2} &\ overline {0}\\
\ hline\ overline {2} &\ overline {2} &\ overline {0} &\ overline {1}
\ end {array}\]

Ejercicio\(7.4.5\).

Hacer una tabla que muestre los resultados de:

1. resta módulo 3
2. multiplicación módulo 3

(Escribe cada una de las entradas de tu tabla como cualquiera\(\overline{0}, \overline{1}\) o\(\overline{2}\).)

7.4B. Los enteros módulo\(n\).

La discusión anterior puede generalizarse para aplicar con cualquier entero\(n\) en lugar de 3. Esto da como resultado aritmética modular.

Definición\(7.4.6\).

Arreglar algún número natural distinto de cero\(n \in \mathbb{N}^{+}\).

1. Para cualquier entero\(k\), usamos\([k]_{n}\) para denotar la clase de equivalencia de\(k\) bajo módulo de congruencia\(n\). Cuando\(n\) es claro desde el contexto, podemos escribir\(\overline{k}\), en lugar de\([k]_{n}\).
2. El conjunto de estas clases de equivalencia se llama el módulo enteros\(n\). Se denota\(\mathbb{Z}_{n}\).
3. Los módulos de suma, resta y multiplicación\(n\) se definen por:
   • \(\bar{a}+{ }_{n} \bar{b}=\overline{a+b}\),
   • \(\bar{a}-{ }_{n} \bar{b}=\overline{a-b}\), y
   • \(\bar{a} \times_{n} \bar{b}=\overline{a b}\).

(Cuando\(n\) es claro desde el contexto, generalmente escribimos\(+\),\(−\), y\(\times\), en lugar de\(+_{n}\),\(−_{n}\), y\(\times_{n}\).)

Tenga en cuenta que\(\# \mathbb{Z}_{n}=n\). Más precisamente:

Proposición\(7.4.7\).

Para cualquier\(n \in \mathbb{N}^{+}\), tenemos\[\mathbb{Z}_{n}=\{\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\}\]

y todos\(\overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1}\) son distintos.

Ejemplo\(\PageIndex{1}\)

Simplificar\((\overline{17}-\overline{5}) \times(\overline{21}+\overline{11})\) en\(\mathbb{Z}_{7}\).

Solución

Tenemos\ [\ begin {aligned}
(\ overline {17} -\ overline {5})\ times (\ overline {21} +\ overline {11}) & =(\ overline {3} -\ overline {5})\ times (\ overline {0} +\ overline {4}) =( 3-5)\ times (\ overline {0+4})\
&=\ overline {-2}\ times\ overline {4} =\ overline {5}\ times\ overline {4} =\ overline {5\ times 4 } =\ overline {20} =\ overline {6}.
\ end {alineado}\]

Ejercicio\(7.4.9\).

1. Simplificar\((\overline{17}-\overline{5}) \times(\overline{21}+\overline{11})\) en\(\mathbb{Z}_{5}\).
2. Simplificar\(\overline{32}+(\overline{23} \times \overline{16})\) en\(\mathbb{Z}_{9}\).
3. Simplificar\((\overline{25} \times \overline{35})+(\overline{18}-\overline{12})\) en\(\mathbb{Z}_{12}\).
4. Hacer tablas que muestren los resultados de:
   1. adición módulo 4.
   2. resta módulo 5.
   3. multiplicación módulo 6.
5. Encontrar\(x, y \in \mathbb{Z}_{12}\), tal que\(x \neq \overline{0}\) y\(y \neq \overline{0}\), pero\(x y=\overline{0}\).