Lucha por entender los fundamentos del sistema completo de residuos

Question

Me cuesta mucho entender la aritmética literal que se aplica para encontrar un sistema completo de residuos de módulo $n$ . A continuación, la definición que ofrece mi libro de texto junto con un ejemplo.

Dejemos que $k$ y $n$ sean números naturales. Un conjunto $\{a_1,a_2,...,a_k\}$ se denomina sistema de residuos completo canónico módulo $n$ si cada número entero es congruente módulo $n$ a exactamente un elemento del conjunto

Me cuesta entender cómo interpretar esta definición. Dos enteros, $a$ y $b$ son "congruentes módulo $n$ "si tienen el mismo resto cuando se dividen por $n$ . Así que el conjunto $\{a_1,a_2,...,a_k\}$ serían todos los enteros que comparten un cociente con $b$ dividido por $n$ ?

Después de entender la definición, este es un ejemplo sencillo que proporciona mi libro de texto

Encuentre tres sistemas de residuos modulares $4$ el sistema de residuos completo canónico, uno que contiene números negativos y otro que no contiene dos números consecutivos

Mi primer punto de confusión es "modulo $4$ ". $a{\space}mod{\space}n$ es el resto de la división euclidiana de $a$ por $n$ . Entonces, ¿qué significa simplemente "módulo $4$ "? ¿Qué aritmética literal realizo para encontrar un sistema de residuos completo utilizando "modulo $4$ "?

Answer 1

Preliminar: La definición es confusa porque es pas suponiendo que $k = n$ . Usted se ser capaz de demostrar $k = n$ más tarde pero en matemáticas no incluimos cualquier cosa en una definición que podemos probar más tarde.

La definición de un sistema completo de residuos es una colección de enteros $\{a_j\}$ de modo que para cualquier entero, ese entero será congruente (tendrá el mismo resto) con exactamente un de esos enteros.

En otras palabras, y probablemente una definición mucho más directa, Para cada posible resto, habrá exactamente un entero con ese resto.

Por ejemplo, si $n = 7$ el sistema de residuos completo más fácil y obvio sería simplemente $\{0,1,2,3,4,5,6\}$ . Todos los números enteros tienen un resto $0,1,2,3,4,5,6$ y esos son precisamente los números que hay.

Otro sistema completo podría ser $\{63, 8, 15, -4, 32, 75, 146\}$ . Si un número entero $b$ tiene un remanente $0$ es congruente con $63$ . $63$ representa todos los enteros con resto $0$ . Y si $b$ tiene un remanente $8$ entonces $b$ es congruente con $8$ . $8$ representa todos los enteros con resto $1$ .... Y así sucesivamente.

Cada resto se representa exactamente una vez.

Y eso es lo que significa un sistema de residuos completo. Un residuo es una representación de una clase de residuos (todos los enteros con resto $4$ por ejemplo, están representados por $32\equiv 4 \pmod 7$ por ejemplo). Y un completa sistema de residuos significa que cada residuo está representado.

Y como hay $n$ posibles restos habrá $n$ elementos del sistema por lo que si el sistema es $\{a_1, ...., a_k\}$ entonces $k = n$ . (Si fuera yo, ni siquiera plantearía la idea de que esto podría estar en duda. Sólo confunde las cosas la primera vez que se ve la definición).

.....

De acuerdo. Para hacer un sistema de residuos completo $\pmod 4$ necesitas encontrar un $\{a_1, a_2, ..... , a_k\}$ eran para cada número entero $-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,....$ es congruente con uno de ellos.

Así que necesitamos y $a_1\equiv -6\pmod 4$ . Bueno $-6\equiv 2 \pmod 4$ así que dejemos que $a_1 = 2$ . Y necesitamos algo $\equiv -5 \pmod 4$ . Nosotros $-5\equiv 3 \pmod 4$ y $15 \equiv 3 \pmod 4$ y $15 \equiv -3 \pmod 4$ así que usemos $a_2 = 15$ .

Y necesitamos algo $\equiv - 4 \pmod 4$ . Bueno $-4 \equiv 0 \equiv 28\pmod 4$ por lo que vamos a utilizar $a_3 = 28$ . Y necesitamos algo $\equiv -3\pmod 4$ pero $-3\equiv 1 \equiv 48321 \pmod 4$ . Así que vamos a dejar que $a_4 = 48321$ .

Y necesitamos algo $\equiv -2\pmod 4$ . Pero $-2 \equiv 2 = a_1$ así que ya lo tenemos. De hecho, parece que tenemos uno de cada.

Así que $\{2, 15,28, 48321\}$ parece estar completo.

Si $b$ es un número entero tenemos $b = 4k$ o $4k + 1$ o $4k + 2$ o $4k + 3$ .

Si $b = 4k$ entonces $b \equiv 28\pmod 4$ . Y si $4k + 1$ entonces $b\equiv 48321$ . Y si $b = 4k + 2$ entonces $b \equiv 2\pmod 4$ y si $b= 4k + 3$ entonces $b\equiv 15\pmod 4$ .

Así que ....

la definición es:

$\{2, 15,28, 48321\}$ se denomina sistema de residuos completo canónico módulo n si cada número entero es congruente módulo n $4$ a exactamente un elemento del conjunto

Bueno, eso es cierto así que $\{2, 15,28, 48321\}$ es un sistema de residuos completo.

Eso es todo.

Answer 2

Puede resultar útil comprender el trasfondo conceptual general que subyace a esta definición. La congruencia es un relación de equivalencia (igualdad generalizada) por lo que divide los enteros en clases de equivalencias, aquí $\,[a] = a + n\Bbb Z\,$ es la clase de todos los enteros $\equiv a\pmod{n}.\,$

Conceptualmente, la aritmética modular es en realidad trabajar con estas clases, por ejemplo, el regla de la suma de congruencias $\,a'\equiv a,\,b'\equiv b\Rightarrow a'+b'\equiv a+b\,$ equivale a decir que $\,[a]+[b] = [a+b]\,$ es una adición bien definida en las clases. Lo mismo ocurre con la multiplicación, por lo que estas clases heredan la suma y la multiplicación de los enteros. Más información en heredan las leyes del anillo de $\,\Bbb Z,\,$ es decir, leyes asociativas, conmutativas y distributivas. Así, las clases gozan de la misma estructura algebraica (de anillo) que los enteros $\Bbb Z,\,$ por lo que podemos realizar la aritmética con ellos al igual que con los enteros.

Pero a la hora de calcular suele ser más cómodo trabajar con números que con conjuntos (clases), por lo que solemos elegir representantes convenientes ("formas normales") para cada clase. Un sistema completo de residuos es precisamente eso. La elección más común aquí es la menos natural en $[a],$ que es simplemente su resto ("residuo") $= a\bmod n,\,$ por lo que este sistema completo de representantes $\bmod n\,$ es $\,\{0,1,\ldots, n-1\}.\,$ Otra opción común son las repeticiones de menor valor absoluto, por ejemplo $\{0,\pm1,\pm2\}\bmod 5$ .

Puede ser útil considerar la analogía con las fracciones. Aquí la relación de congruencia para la equivalencia de fracciones es $\,a/b \equiv c/d\iff ad = bc.\,$ y la forma normal común de las reps son de nuevo las reps de menor término, es decir, fracciones con numerador y denominador coprimos. La regla de la suma anterior no suele demostrarse a nivel elemental, lo que debería hacerte reflexionar sobre por qué aceptaste su verdad sin pruebas. Esto se rectificará si se estudian los campos de fracciones (o localizaciones) en el álgebra abstracta (que también generaliza la aritmética modular en el estudio de los anillos generales de cocientes (residuos), y las congruencias, y su relación ).

Nota: $ $ La elección del resto como forma normal rep también funciona en anillos de polinomios sobre un campo (por ejemplo, se obtienen los números complejos $\,\Bbb C \cong \Bbb R[x]/(x^2+1)\,$ como el sistema completo de repeticiones de polinomios reales mod $\,x^2+1),\,$ o en cualquier dominio con un algoritmo euclidiano (computable). Pero, en general, puede que no haya ninguna forma natural (computable) de elegir dichas formas normales, por lo que puede que no tengamos más remedio que trabajar con el clases ellos mismos.

Answer 3

Puedes hacer un dibujo para el módulo 6. Coge una hoja de papel y colócala con la dimensión más larga en horizontal. Con un bolígrafo oscuro y una regla, dibuja siete líneas horizontales que atraviesen completamente la página. Aproximadamente en la mitad de la página escribe los enteros de 0 a 5 UNO POR REGIÓN, empezando por la parte inferior.

Introduce todos los demás números enteros (o al menos muchos de ellos) de la siguiente manera: En cada región, suma repetidamente 6 al número de la izquierda hasta que se te acabe el papel.

Y luego vuelve al centro y resta repetidamente 6 a cada número de la derecha.

(Un sistema completo de residuos será de 6 enteros, sin que dos sean de la misma región).