¿Por qué "trabajar en $\mathbb {Z}_m$ "¿Esencialmente es lo mismo que "trabajar con congruencias módulo m"?

Question

Debido a mi ignorancia, sólo superficialmente conocer la definición de congruencia en la teoría de los números:

Para un número entero positivo dado $n$ dos enteros $a$ y $b$ se llaman congruentes módulo $n$ , escrito $a\equiv b\pmod{n}$ si $ab$ es divisible por $n$ (o, por el contrario, si $a$ y $b$ tienen el mismo resto cuando se dividen por $n$ ).

Motivado por los comentarios y las respuestas a la pregunta:

resolver $x^{12}-x^{10}=2$ en el campo $\mathbb {Z}_{11}$ ,

Me gustaría publicar la pregunta aquí:

¿Por qué "trabajar en $\mathbb {Z}_m$ " esencialmente lo mismo que "trabajar con congruencias módulo $m$ "?

Edición: De acuerdo con el comentario de Qiaochu, he añadido la definición de ${\mathbb Z}_n$ que aprendí aquí.

Dejemos que $n$ sea un número entero mayor o igual que $2$ y considerar el conjunto ${\mathbb Z}_n=\{0,1,2,\cdots,n-1\}$ . Para dos enteros cualesquiera $a$ y $b$ en ${\mathbb Z}_n$ , defina $a\oplus b$ para ser el resto cuando la suma habitual, $a+b$ se divide por $n$ . Entonces, para cada $a$ y $b$ en ${\mathbb Z}_n$ , $a\oplus b$ es único interger en ${\mathbb Z}_n$ que es congruente con $a+b\pmod{n}$ . Con esta operación, $({\mathbb Z}_n,\oplus)$ es un grupo abeliano finito de orden $n$ llamado grupo aditivo de los enteros módulo $n$ .

Answer 1

Hay muchas maneras de pensar en $\mathbb{Z}_m$ y exactamente la forma en que lo piensas puede ser el problema. Veo por los comentarios que usted piensa en $\mathbb{Z}_m$ como el set $\{0,1,2,\ldots,m-1\}$ con una suma/multiplicación especial definida. Esto es probablemente lo que está bloqueando su realización de la conexión con congruencias.

Así que, primero, voy a "llegar a" $\mathbb{Z}_m$ desde "el otro extremo", por así decirlo, llegando a ella partiendo de las congruencias, y mostrando finalmente que se puede identificar con la forma en que se está pensando. Más adelante, lo abordaré desde el punto de vista de los anillos, los ideales y los cocientes.

A partir de las congruencias

Así que vamos a trabajar con la definición de congruencia módulo $m$ primero. Me limito a los "no negativos". $m$ " sólo por comodidad; la definición no lo requiere realmente.

Definición. Dejemos que $m$ sea un número entero no negativo. Decimos que dos enteros $a$ y $b$ "son congruentes modulo $m$ ", escrito $$a \equiv b\pmod{m}$$ si y sólo si $m|b-a$ . También decimos que " $a$ es congruente con $b$ modulo $m$ ".

Teorema. La relación "es congruente con el módulo $m$ " es una relación de equivalencia sobre los enteros. Es decir:

1. La relación es reflexiva: para todos los enteros $a$ , $a\equiv a \pmod{m}$ .
2. La relación es simétrica: para todos los enteros $a$ y $b$ , si $a\equiv b\pmod{m}$ entonces $b\equiv a\pmod{m}$ .
3. La relación es transitiva: para todos los enteros $a$ , $b$ y $c$ , si $a\equiv b\pmod{m}$ y $b\equiv c\pmod{m}$ entonces $a\equiv c\pmod{m}$ .

Prueba.

1. Desde $0$ es un múltiplo de cada número entero, $m|a-a=0$ para todos $a$ .

2. Si $a\equiv b\pmod{m}$ entonces $m|b-a$ . Entonces existe un número entero $k$ tal que $mk=b-a$ por lo tanto, $m(-k) = a-b$ Así que $m|a-b$ Por lo tanto $b\equiv a\pmod{m}$ .

3. Si $m|b-a$ y $m|c-b$ entonces $m$ divide la suma $(b-a)+(c-b)=c-a$ Así que $a\equiv c\pmod{m}$ . QED

Por el Teorema fundamental de las relaciones de equivalencia la relación de equivalencia "es congruente con el módulo $m$ " da una partición de $\mathbb{Z}$ en clases de equivalencia. Dado un número entero $a$ , denotémoslo por $[a]_m$ la clase de equivalencia módulo $m$ de $a$ eso es, $$[a]_m = \{b\in\mathbb{Z}\mid a\equiv b\pmod{m}\}.$$ Tenga en cuenta que $[a]_m=[b]_m$ si y sólo si $a\equiv b \pmod{m}$ . Si $m$ se entiende por el contexto, nos limitaremos a escribir $[a]$ .

Ahora tenemos un conjunto que tiene como elementos las clases de equivalencia módulo $m$ . ¿Cuántos elementos hay?

Teorema. Dejemos que $m$ sea un número entero no negativo.

1. Si $m=0$ entonces $[a]_m=[b]_m$ si y sólo si $a=b$ por lo tanto, las clases de equivalencia modulo $m$ son monotonales, y "congruente módulo $0$ " es lo mismo que la igualdad. El número de clases de congruencia módulo $0$ es $\aleph_0$ la cardinalidad de $\mathbb{Z}$ .

2. Si $m\gt 0$ entonces $[a]_m=[b]_m$ si y sólo si el resto de dividir $a$ por $m$ es el mismo que el resto de la división de $b$ por $m$ . En particular, todo número entero es congruente módulo $m$ a uno y sólo uno de $0$ , $1$ , $2,\ldots,m-1$ . El número de clases de congruencia módulo $m$ es exactamente $m$ .

Prueba.

1. Si $m=0$ entonces $a\equiv b\pmod{0}$ si y sólo si $0$ divide $b-a$ si y sólo si existe un número entero $k$ tal que $0k=b-a$ si y sólo si $b-a=0$ si y sólo si $a=b$ . Así que "congruente módulo $0$ " es lo mismo que "igual", y el resto de la cláusula sigue.

2. Supongamos que $a\equiv b\pmod{m}$ . Entonces $m|b-a$ por lo que existe un número entero $k$ tal que $b-a = km$ . Ahora escribe $a=qm + r$ con $0\leq r\lt m$ (para que $r$ es el resto cuando dividimos $a$ por $m$ ). Entonces $b=km+a = km+qm+r = (k+q)m+r$ . Por la unicidad del cociente y del resto, $r$ es el resto de la división de $b$ por $m$ Así que $a$ y $b$ tienen el mismo resto.

   A la inversa, supongamos que $a$ y $b$ tienen el mismo resto cuando se dividen por $m$ . Entonces existe $r$ , $0\leq r\lt m$ y los enteros $q_1$ y $q_2$ , de tal manera que $a=q_1m+r$ y $b=q_2m+r$ . Entonces $b-a = (q_2m+r)-(q_1m+r) = (q_1-q_1)m$ Así que $m|b-a$ Por lo tanto $a\equiv b\pmod{m}$ .

   Los posibles restos al dividir un entero por $m$ son $0$ , $1$ , $2,\ldots,m-1$ y cada uno de ellos es su propio resto cuando se divide por $m$ . Por lo tanto, si $a=mq+r$ , $0\leq r\lt m$ entonces $r$ es uno y sólo uno de $0$ , $1$ , $2,\ldots,m-1$ y $a$ es congruente con eso. Así que todo entero es congruente módulo $m$ a al menos uno de $0$ , $1$ , $2,\ldots,m-1$ . Supongamos ahora que $r$ y $s$ son cada uno igual a uno de $0$ , $1,\ldots,m-1$ y $r\equiv s\pmod{m}$ queremos demostrar que $r=s$ . Supongamos sin pérdida de generalidad que $s\geq r$ . Entonces $m|s-r$ Pero $0\leq s-r\lt m$ la única posibilidad es $s-r=0$ Así que $s=r$ .

   Así, cada uno de $[0]_m$ , $[1]_m,\ldots,[m-1]_m$ es una clase de congruencia distinta módulo $m$ y toda clase de congruencia módulo $m$ es uno de ellos, por lo que hay exactamente $m$ clases de congruencia módulo $m$ . QED

Arreglar $m\gt 0$ . Tenemos un conjunto de clases de congruencia de números enteros módulo $m$ . Si utilizamos la notación estándar para el conjunto de clases de congruencia módulo una relación de equivalencia, tendríamos que escribir algo como $$\mathbb{Z}/\equiv\pmod{m}\qquad\text{or}\qquad \mathbb{Z}/\equiv_m.$$ Ambos son un poco torpes, así que en su lugar utilizamos un símbolo especial para este caso particular: el conjunto se denotará $\mathbb{Z}_m$ . Es decir: $$\mathbb{Z}_m = \Bigl\{ [a]_m \Bigm| a\in\mathbb{Z}\Bigr\}.$$

Tenga en cuenta que cada elemento de $\mathbb{Z}_m$ tiene muchos "nombres". Por ejemplo, con $m=4$ tenemos que el elemento $[0]_4$ es lo mismo que $[4]_4$ , como $[8]_4$ , como $[-12]_4$ y en general, $[a]_4$ es lo mismo que $[a+4k]_4$ para cualquier número entero $k$ . Si queremos trabajar con $\mathbb{Z}_m$ Tenemos dos opciones:

• Hay que tener en cuenta que las cosas pueden tener varios nombres diferentes; eso significa que si intentamos definir funciones o propiedades sobre los elementos de $\mathbb{Z}_m$ Tenemos que asegurarnos de que son bien definido que no dependen del "nombre" que tengamos para el elemento (véase más adelante); o
• Elige un "conjunto distinguido de representantes". Es decir, elige un específico , fijo para cada uno de los elementos de $\mathbb{Z}_m$ y se ciñen a esa etiqueta en todo momento. Por ejemplo, una cosa común para hacer con $\mathbb{Z}_m$ es elegir $[0]_m$ , $[1]_m$ , $[2]_m,\ldots,[m-1]_m$ como "etiquetas distinguidas". Para $m=5$ por ejemplo, nos ceñiríamos por completo a $[0]_5$ , $[1]_5$ , $[2]_5$ , $[3]_5$ y $[4]_5$ aunque cada una de estas clases tenga infinitamente otros nombres. (a veces resulta conveniente escoger como etiquetas las etiquetas $[a]_m$ con $|a|$ mínimo; para $m=5$ Por ejemplo, se trabajaría con $[0]_5$ , $[1]_5$ , $[-1]_5$ , $[2]_5$ y $[-2]_5$ ).

(Seguramente ya se imaginan cómo vamos a llegar a $\mathbb{Z}_m$ "ser" el conjunto $\{0,1,2,\ldots,m-1\}$ ...)

Ahora, la cosa es que $\mathbb{Z}$ no es sólo un conjunto; tiene buenas operaciones como $+$ y $\times$ . Queremos ver si podemos conseguir $\mathbb{Z}_m$ para "heredar" estas operaciones. Y podemos hacerlo. Primero, definámoslas utilizando la primera opción anterior:

Definición. Dejemos que $m\gt 0$ . Definimos la "adición en módulo" como $m$ ", $+_m$ para ser la operación binaria sobre $\mathbb{Z}_m$ definido por: $$[a]_m +_m [b]_m = [a+b]_m,$$ y "multiplicación moudlo $m$ ", $\times_m$ , por $$[a]_m \times_m [b]_m = [a\times b]_m,$$ donde las operaciones del lado derecho de las definiciones son las operaciones habituales de los números enteros.

Porque cada elemento de $\mathbb{Z}_m$ tiene "diferentes nombres", pero la definición está haciendo uso de la nombres específicos que elijamos, tenemos que asegurarnos de que estas dos operaciones bien definido . Es decir, si sustituimos la etiqueta $[a]_m$ por un nombre diferente para la misma clase, $[x]_m$ ¿el resultado de añadir $[a]_m$ y $[b]_m$ sea el mismo que el resultado de sumar $[x]_m$ y $[b]_m$ ? Ellos debe si va a ser una función, pero no lo sabemos de antemano porque la operación se define en términos de la etiqueta no en términos de la objeto y cada objeto tiene muchas etiquetas diferentes. Por eso hay que asegurarse de que las operaciones estén bien definidas. Es decir, tenemos que asegurarnos de que:

Teorema. Si $[a]_m = [x]_m$ y $[b]_m = [y]_m$ entonces $[a+b]_m=[x+y]_m$ y $[ab]_m = [xy]_m$ . Es decir, $+_m$ y $\times_m$ están bien definidos.

Prueba. Porque $[r]_m = [s]_m$ si y sólo si $r\equiv s\pmod{m}$ el teorema es equivalente a las dos afirmaciones siguientes:

1. Si $a\equiv x\pmod{m}$ y $b\equiv y\pmod{m}$ entonces $a+b\equiv x+y\pmod{m}$ ("congruencias módulo $m$ puede añadirse");
2. Si $a\equiv x\pmod{m}$ y $b\equiv y\pmod{m}$ entonces $ab\equiv xy\pmod{m}$ ("congruencias módulo $m$ se puede multiplicar").

De hecho, si $m|x-a$ y $m|y-b$ entonces $m$ divide su suma, $(x-a)+(y-b) = (x+y)-(a+b)$ Por lo tanto $a+b\equiv x+y\pmod{m}$ . Para la cláusula de multiplicación, si $m$ divide $x-a$ , entonces divide $(x-a)b = xb-ab$ . Si $m$ divide $y-b$ , entonces divide $x(y-b) = xy-xb$ . Desde $m$ divide ambos $xb-ab$ y $xy-xb$ divide su suma, por lo que $m|(xy-xb)+(xb-ab) = xy-ab$ . Por lo tanto, $ab\equiv xy\pmod{m}$ .

Así que $+_m$ y $\times_m$ están bien definidos. QED

Ahora supongamos que queremos definir la suma y la multiplicación en módulo $m$ utilizando la segunda opción comentada anteriormente. En primer lugar, acordamos nombres específicos para los elementos de $\mathbb{Z}_m$ . Sigamos con $[0]_m$ , $[1]_m$ , $[2]_m,\ldots,[m-1]_m$ exclusivamente. Entonces definiríamos: $$\begin{align*} \ [a]_m +_m [b]_m &= \left\{\begin{array}{ll} \ [a+b]_m &\text{if }0\leq a+b\lt m;\\ \ [a+b-m]_m &\text{if }m\leq a+b.\end{array}\right.\\ \ [a]_m \times_m [b]_m &= [ab-km]_m\quad\text{where }k\in\mathbb{Z}\text{ is such that }km\leq ab\lt (k+1)m. \end{align*}$$

La ventaja de la segunda definición es que no hay ninguna duda de que la operación está bien definida. La desventaja es que es difícil de utilizar en la práctica. Por ejemplo, probar que $\times_m$ es asociativo usando la primera definición (una vez que hemos establecido que está bien definido) es muy fácil: simplemente se hereda del hecho de que es asociativo en $\mathbb{Z}$ : $$\begin{align*} ([a]_m\times_m[b]_m)\times_m[c]_m &= [ab]_m\times_m[c]_m &\quad&\text{(by definition of )}\times_m\text{)}\\ &= [(ab)c]_m &&\text{(by definition of }\times_m\text{)}\\ &= [a(bc)]_m &&\text{(since }(ab)c=a(bc)\text{ in }\mathbb{Z}\text{)}\\ &= [a]_m\times_m[bc]_m &&\text{(by definition of }\times_m\text{)}\\ &= [a]_m\times_m([b]_m\times_m[c]_m).&&\text{(by definition of }\times_m\text{)}\end{align*}$$ Demostrarlo utilizando la definición 2 es mucho más engorroso.

Pero ambos son completamente equivalentes, en el sentido de que se puede demostrar que definen exactamente las mismas operaciones sobre $\mathbb{Z}_m$ .

Porque $+_m$ y $\times_m$ se definen como "esencialmente iguales" a las operaciones $+$ y $\times$ para los números enteros, a menudo omitimos el subíndice, dejando que se entienda por el contexto. Así que simplemente escribimos $[a]_m+[b]_m$ y si además dejamos caer el $m$ para que se entienda por el contexto, entonces simplemente escribiríamos $[a]+[b]$ .

De ahí a dejar caer también los paréntesis no hay nada que objetar. Así que escribiríamos $\mathbb{Z}_m = \{0,1,2,\ldots,m-1\}$ (aunque nosotros realmente significa que el clases de congruencia de $0$ , $1$ , $2,\ldots,m-1$ , no los propios enteros), y escribir allí las operaciones como $+$ y $\times$ (aunque nosotros realmente significan las operaciones $+_m$ y $\times_m$ definida en las clases de congruencia).

Cociente de un anillo

De hecho, el enfoque de tener varios nombres para cada clase y definir las operaciones sobre las clases en términos de operaciones del conjunto original es la práctica habitual al construir cocientes algebraicos (de grupos, anillos, retículos, etc.).

Aquí, tenemos un anillo , $\mathbb{Z}$ y un ideal $m\mathbb{Z}$ que consiste en todos los enteros que son múltiplos de $m$ . Utilizamos el ideal $m\mathbb{Z}$ para definir una relación de equivalencia en $\mathbb{Z}$ por: $$a\sim b\quad\Longleftrightarrow\quad b-a\in m\mathbb{Z}.$$ Porque $\mathbb{Z}$ es un ideal (de hecho, basta con que sea un subgrupo para ello), $\sim$ es una relación de equivalencia en $\mathbb{Z}$ . De hecho, $$a\sim b\quad\Longleftrightarrow\quad a\equiv b\pmod{m}.$$ Así que el anillo de cociente $\mathbb{Z}/m\mathbb{Z}$ que consiste en las clases de congruencia módulo $m\mathbb{Z}$ es exactamente lo mismo como el conjunto de clases de congruencia módulo $m$ , $\mathbb{Z}_m$ con las operaciones $+_m$ y $\times_m$ que hemos definido anteriormente.

Sin embargo, como lo estamos definiendo como un cociente de anillos, todas las propiedades que se cumplen para cualquier cociente de anillos (se tiene una estructura de anillos inducida por la estructura de anillos del anillo original, por ejemplo) se cumplen "automáticamente" para $\mathbb{Z}_m$ .

Pero como las dos construcciones dan lugar a la mismo conjunto subyacente con las mismas operaciones trabajando en el cuadrilátero $\mathbb{Z}/m\mathbb{Z}$ con las operaciones inducidas es lo mismo que trabajar en el anillo $\mathbb{Z}_m$ con las operaciones $+_m$ y $\times_m$ que a su vez es lo mismo que trabajar directamente con congruencias módulo $m$ .

Añadido. El hecho de tener una relación de equivalencia que corresponde a un ideal es en realidad una instancia de congruencias (mencionado por Bill Dubuque en un comentario a la pregunta original). Puede ver una discusión sobre esto en mi respuesta a la pregunta de por qué los cocientes de grupo se definen sólo para los subgrupos normales. Por supuesto, desde el punto de vista del grupo esto no importa con $\mathbb{Z}$ y $m\mathbb{Z}$ , ya que el primero es abeliano por lo que todo subgrupo es normal; pero se puede intentar hacer el desarrollo paralelo para anillos e ideales y establecer los mismos teoremas. Son un caso especial de los teoremas más generales del álgebra universal.

Answer 2

$\mathbb{Z}_m$ se define como el cociente $\mathbb{Z}/m\mathbb{Z}$ . Es decir, dos enteros $a$ , $b$ en $\mathbb{Z}_m$ se consideran iguales si y sólo si $$ a-b \in m\mathbb{Z}. $$ Esto significa que $a$ , $b$ son iguales si y sólo si existe algún número entero $k$ tal que $a-b = mk$ .

Del mismo modo, trabajando con congruencias, se tiene que $a\equiv b \:(\text{mod }m)$ si y sólo si $m | (a-b)$ que es lo mismo que decir que existe algún número entero $k$ tal que $a-b=mk$ . En resumen, pues, $$ a=b\text{ in }\mathbb{Z}_m \iff a-b=mk\text{ for some }k \in \mathbb{Z} \iff a \equiv b\ (\text{mod }m). $$

Answer 3

$\mathbb Z_n$ suele introducirse primero como un grupo aditivo finito de orden $n$ (que es diferente del grupo infinito $\mathbb Z$ con adición), denotado ( $\mathbb Z_n, +_n$ ).

Para responder a tu pregunta: sí, más o menos. La operación sobre el grupo finito $\mathbb Z_n$ es la adición en módulo $n$ , donde $n$ es un número entero positivo, y los elementos del grupo pueden considerarse como la representación de clases de equivalencia , a menudo denominado clases de residuos módulo n , donde la adición modulo $n$ es la relación de equivalencia, y tal que cada elemento de $\mathbb Z$ es congruente módulo n a exactamente uno de los elementos de $\mathbb Z_n$ . De esta manera, tenemos que todo $\mathbb Z$ puede dividirse en $n$ clases de equivalencia módulo $n$ .

Ejemplo.
$\mathbb Z_4 = \{0, 1, 2, 3\}$ es un grupo cíclico finito de orden 4 bajo adición modulo $n$ . $0$ es el elemento de identidad del grupo, $1$ es un generador del grupo (al igual que $3$ ). Todo número entero, cuando se divide por $4$ o un múltiplo integral de $4$ tiene un remanente de $0$ , $1$ , $2$ o $3$ .

Una vez que pase de los grupos a los anillos y campos, aprenderá mucho más sobre $\mathbb Z_n$ ¡! En realidad, puede aprender mucho más sobre $\mathbb Z_n$ aquí en Math.SE, ¡simplemente estudiando la respuesta de Arturo a tu pregunta!

Answer 4

La respuesta es sí porque el mapa natural $\mathbb Z \to \mathbb Z_m$ es un homomorfismo de anillo con núcleo $m\mathbb Z$ . En otras palabras, respeta las congruencias módulo $m$ .