Aritmética de módulos y aplicación a criterios de divisibilidad

[argentinator]

En vistas de que este tema se hace cada vez más común, y de lo básico que resulta, parece conveniente fijar un thread con los resultados básicos pertinentes.
Lo que expongo aquí es un primer intento. Si ustedes consideran que hay que completar la información o cambiar algo, indíquenlo.

También se puede ir agregando en el futuro más propiedades relacionadas con congruencias, que sean aplicables a distintas áreas de la Teoría de Números.
Sugieran ustedes qué agregar.

Sección 1. Números enteros. Generalidades.

Sin entrar en muchas definiciones complicadas, vamos a aceptar que todos sabemos o entendemos qué clase de números son los enteros.
Designaremos con al conjunto de los números enteros, e indiquemos intuitivamente su "definición":

Como puede verse, los enteros negativos vienen desde el infinito negativo, pasan por 0, y siguen siempre de 1 en 1 yendo hacia el infinito positivo.

Denotamos al subconjunto de enteros positivos y al subconjunto de enteros negativos:

Asumimos que en tenemos definidas dos operaciones binarias, suma y producto, que son conmutativas, asociativas, y cumplen la ley distributiva.
Además, el 0 es neutro para la suma, el 1 es identidad para el producto, y la suma es invertible, vale decir, todo entero tiene un opuesto tal que .

Sin embargo, no todo número entero tiene inverso multiplicativo.
De hecho, los únicos enteros invertibles son el 1 y el -1, y cada uno de ellos es su propio inverso.

Se cumplen también las reglas de los signos, entre muchas otras propiedades conocidas por todos nosotros.

En todo nuestro trabajo posterior asumiremos que nuestro campo de trabajo será el conjunto de números enteros con las operaciones de suma y producto.

Una propiedad muy importante, que asumiremos sin demostración, es el Principio de Inducción:

Todo subconjunto inductivo de es igual a

y está también su propiedad equivalente: el Principio de Buena Ordenación, el cual enunciaremos en un formato aplicable a todos los enteros:

Todo subconjunto no vacío de acotado inferiormente, tiene un elemento mínimo.
Igualmente:
Todo subconjunto no vacío de acotado superiormente, tiene un elemento máximo.

Finalmente convengamos en denotar al valor absoluto de un número entero .

[argentinator]

Sección 2. Divisibilidad.

Definición (Divisibilidad). Dados dos números enteros , se dice que es divisor de si, y sólo si, existe un número entero tal que . También se suele decir que divide a , o que es múltiplo de . La notación que se usa para indicar esta relación es: .
En símbolos, tendríamos pues que:

si, y sólo si

En el siguiente Teorema hacemos un sumario de los resultados básicos de divisibilidad, y la demostración la dejamos como ejercicio.

Teorema 1 (propiedades varias de la divisibilidad) Sean números enteros.

• , .
• , .
• .
• Si entonces (o sea, no divide a ).
• Si entonces .
• Si y entonces

Observemos cómo la última propiedad nos indica que el "tamaño" de un divisor necesariamente es menor que el de su múltiplo.
La excepción a esta regla es el número 0.

En cuanto a la divisibilidad como relación de orden, podemos decir lo siguiente:

Teorema 2 (cuasi-orden de la relación de divisibilidad). La relación de divisibilidad es un cuasi-orden parcial en .

Esto quiere decir que:

• Reflexividad: Si entonces .
  
• Cuasi-Antisimetría: Si , y , entonces .
  
• Transitividad: Si ,  y , entonces .
  

La demostración la dejamos como ejercicio.

El término cuasi-orden parcial me lo acabo de inventar, y tan sólo pone de manifiesto que la antisimetría se cumple con una versión con signos. Si y no podemos asegurar que , como en un orden parcial ocurriría, pero sin embargo eso es casi cierto, porque en realidad se obtiene que los valores absolutos de y coinciden.

Si restringimos la divisivilidad al conjunto de enteros positivos, se obtiene un orden parcial.

Sin embargo, aún en ese caso el orden obtenido no es total, porque hay al menos un par de enteros positivos que no pueden compararse entre sí.
Por ejemplo, el 2 y el 3 no son el uno divisor del otro.


Definición (Primos, compuestos, coprimos). Sea un número entero distinto de . Se dice que es primo si sus únicos divisores son . Se dice que es compuesto si no es primo.
Dados dos enteros , se dice que son coprimos si los únicos números enteros que son divisores, tanto de como de al mismo tiempo, son y .

Nótese que hemos podido dar la noción de coprimalidad sin apelar al clásico uso del máximo común divisor.

Obsérvese también que es primo si, y sólo si es primo.
Ídem con compuestos.
Los numeros 1, 0, no son primos ni compuestos.

Teorema 3 (Algoritmo de División). Sean entero y entero positivo. Entonces existen únicos enteros tales que

• 
• 

Al número se le llama cociente, y al número se le llama resto.

Si el resto es 0, se escribe .
En ese caso se puede comprobar que son ambos divisores de y además .
Más aún, podemos definir en este caso también .

La operación para enteros con distinto de 0, se llama división, y claramente está definida sólo cuando es divisor de .
De lo contrario, la división no está definida.

La división puede definirse usando otros métodos, pero siguiendo el "tren" de lo que vengo escribiendo, lo más simple que me quedó fue lo que está escrito ahí arriba.

Lema Fundamental de la Aritmética. Todo entero distinto de 1, -1 o 0 es divisible por algun número primo.
Demostración:

Sea entero positivo mayor que 1. Supongamos que no es primo. En ese caso, existe un entero que es divisor de y tal que es distinto de . Tanto como son divisores de , así que podemos suponer que es entero positivo, sin pérdida de generalidad.
Tenemos que . Puede que sea primo o compuesto.
Si fuera primo, habríamos terminado. Así que supongamos que es compuesto.
Denotemos . Aplicando a el mismo procedimiento que aplicamos a , podemos hallar un número entero positivo tal que y .
Supongamos que tras un número finito de pasos, con este mismo procedimiento, hemos hallado números enteros positivos tales que:

*
*

De nuevo, puede que d_k sea primo o compuesto. Si es compuesto, se puede seguir con el procedimiento para hallar un nuevo entero positivo que divide a y tal que .
Sin entrar en demasiados formalismos, digamos que este procedimiento no puede seguir indefinidamente, porque en tal caso tendríamos una sucesión infinita y decreciente de números enteros positivos. Esto no puede ser, porque se contradice el Principio del Descenso Infinito.

Así que hay algún en el que el proceso termina, y ese número es primo.

Teorema 4 (Infinidad de primos). Los números primos son infinitos.

La demostracion queda como ejercicio, y sigue el clasico argumento de Euclides de razonar por el absurdo, o sea, suponer que hay una cantidad finita de primos positivos y definir . Este valor es mayor que todos los primos de la lista, y a su vez resulta indivisible por los otros primos. Y sabemos también que todo número entero que no es primo, es divisible por algún primo. Contradicción.

La lista de números primos positivos forma un conjunto infinito .
Se suele denotar a esta lista con una sucesión subindicada, la cual adoptaremos de aquí en adelante: .
Así, tenemos , etc.
Procuraremos no usar la letra para otra cosa que primos positivos.

Teorema Fundamental de la Aritmética. Dado un número entero , existen únicos enteros positivos primos tales que , únicos exponentes enteros positivos , y un valor ó , de tal manera que:

Lo anterior puede escribirse en la siguiente forma alternativa:

donde los exponentes son números enteros positivos o bien 0, y sólo una cantidad finita de ellos es no nula, de manera que el producto infinito en realidad es siempre finito y tiene pleno sentido (no hace falta plantearse cuestiones de convergencia o problemas con el infinito).


Definición (Máximo Común Divisor) Dados dos números enteros cualesquiera, tales que al menos uno de ellos (digamos ) es distinto de 0, se llama máximo común divisor al máximo número entero positivo que es divisor de y al mismo tiempo.
Se usan las notaciones y también .

En realidad primero habría que probar que tal máximo, existe. Que m, n tienen al menos un divisor positivo común, es obvio porque el 1 divide siempre a ambos.
Si formamos la lista de divisores comunes enteros positivos, dicha lista tendrá un máximo porque sabemos que todo divisor es menor que el valor absoluto de .

Se puede demostrar fácilmente que dos enteros son coprimos si y sólo si . 

Identidad de Bezout. Sean números enteros con . En tal caso, existen enteros , tales que .

Teorema 5 (coprimalidad y combinaciones lineales). Dados dos enteros , resulta que ellos son coprimos entre sí si, y sólo si, existen enteros tales que .



Definición (Mínimo Común Múltiplo) Dados dos números enteros cualesquiera, ambos distintos de 0, se llama mínimo común múltiplo al mínimo número entero positivo que es múltiplo de y al mismo tiempo.
Se usan las notaciones y también .

En principio, existe un número positivo que es múltiplo de m, n, a saber: u = |mn|. Luego existe el mínimo de los números que son múltiplos de m y n a la vez, por la minimalidad de los números naturales. Más aún, se tienen las siguientes desigualdades:

Teorema 6 (mcd y mcm). Sean enteros positivos. Vale la siguiente igualdad:

[argentinator]

Sección 3. Congruencias

Definición (congruencia). Sean números enteros cualesquiera, y sea un entero positivo. Se dice que son congruentes módulo si al aplicar el algoritmo de la división, el resto al dividir por es igual al resto de dividir por . Más precisamente, si , satisfacen , , entonces . En este caso se escribe la siguiente relación, llamada de congruencia módulo :

Yo también uso la siguiente forma, que no sé si aparece en algún libro:

Se puede ver fácilmente que una definición equivalente a la anterior sería la siguiente: si y sólo si es divisor de .

Teorema 1 (toda congruencia es una equivalencia). Dado un entero positivo , la relación de congruencia es una relación de equivalencia. Esto significa que, dados enteros :

• Reflexividad: .
  
• Simetría: Si entonces .
  
• Transitividad: Si , entonces .
  

Como sabemos, toda relación de equivalencia induce una partición del conjunto total en clases de equivalencia.
En este caso, para un entero positivo d, el conjunto de enteros queda particionado en clases de equivalencia, que son:

Así, son todas las clases de equivalencia posibles de la relación de congruencia módulo .

En particular, si es el resto obtenido en el algoritmo de división, se obtiene que:

A veces puede ser útil usar números negativos al operar con congruencias.
Así que observemos que y que el resto de dividir el número por es de nuevo .
Así que:

Teorema 2 (Aritmética elemental de restos) Las operaciones elementales de suma,  producto y potencia de exponente positivo, conservan el resto tras aplicar el algoritmo de la división.

Spoiler: Detalles... (click para mostrar u ocultar)

Para decirlo más precisamente, sean enteros dados, y sea un entero positivo.
Sea también un entero positivo.
Supongamos ahora que en el algoritmo de la división hemos obtenido que:

• 
• 
• 
• 
• 

Entonces se tiene que:

En tal caso, están definidas sin ambigüedad las operaciones aritméticas de suma, resta, producto y potencia entera positiva sobre las clases de equivalencia módulo :

• 
• 
• 

El resultado anterior puede establecerse de forma más clara usando congruencias:

Teorema 3 (aritmética de congruencias) Sean números enteros un entero positivo . Dado un entero positivo , si se cumple que y entonces se tiene que:

• 
• 
• 

Observación importante: La división en general no está permitida en las igualdades que involucran congruencias.

Sin embargo, hay algunos casos en los que sí está permtido dividir:

Teorema 4 (caso que permite dividir en congruencias) Sean números enteros. Sea un entero positivo, y sea entero divisor común de .
Si y si es coprimo con , entonces .

Antes de seguir, hagamos las observaciones súper-básicas siguientes:

Dados se tiene que si y sólo si es divisor de .

Dados se tiene que es divisor de si y sólo si .


Teorema 5 (Otras propiedades de las congruencias). Sean enteros, y sean enteros positivos.

• Si entonces siendo el mínimo común múltiplo de .
• Si y , entonces .
• Si y , entonces .
• Si y y , entonces .

Teorema 6 (producto de divisores coprimos). Sean enteros, y sean enteros positivos. Supongamos además que para par tal que se tiene que . Entonces:

[argentinator]

Sección 4. Criterios de Divisibilidad

Muchas hemos visto criterios de divisibilidad, y nos parecen reglas mágicas que permiten decir si un número dado es o no divisible por 3 o por 9 tan sólo conociendo sus cifras.
No hay nada sobrenaturales en esto, y ahora vamos a ver cómo encontrar criterios de divisibilidad para cualquier divisor .

Primero vamos a trabajar con números representados en base 10, y luego generalizaremos a una base b cualquiera.

Base 10.

Sea un número entero positivo que supondremos fijado en lo que sigue.
Nos interesa saber si un número entero positivo es divisible o no por , conociendo las cifras de , y sin tener que hacer la tediosa operación de dividir.

Para ello, recordemos que si la representacion de con cifras decimales es , quiere decir que el numero tiene cifras decimales, cada una satisfaciendo , y que su valor es igual a:

Ahora bien, dado que es divisor de si y solo si , y dado que las operaciones aritmeticas se conservan modulo , tenemos que para todo numero entero tal que , podemos escribir la congruencia modulo siguiente:

Digamos algo mas, y es que las potencias no pueden tener resto siempre distinto modulo , porque los restos posibles son, a lo sumo, . Así que en algún momento alguno de ellos tendrá que ser repetición de alguno de los anteriores. Más aún, debido a la conservación del producto por congruencias, las sucesivas potencias tendrán que repetirse con el mismo patrón, y de esa manera los restos modulo de las potencias de 10 que siguen se repetirán cíclicamente.

Para saber en con qué exponente se inicia el ciclo de repeticiones de restos, en principio tendremos que buscar a mano las sucesivas potencias hasta detectar que un par se han repetido.
No voy a entrar en mayores detalles por ahora. Quizá más adelante, si surge la inquietud en el público, se pueda ser más exacto.

Llamemos sistema de restos modulo a la lista ordenada de restos tales que , donde es el exponente donde comienza el ciclo de repeticiones, es cualquier entero no negativo, y .

Esto permite dar un criterio de divisibilidad por .

Tenemos ahora, para el número de arriba, lo siguiente:

donde indica el índice tal que .
Hemos tenido que usar una congruencia modulo en el subíndice.

Interpretemos un poco la fórmula de arriba. Tiene dos partes.
La primer parte corresponde a las potencias de 10 que no han entrado aún al ciclo de potencias cuyo resto se repite módulo .
La segunda parte corresponde a las potencias de 10 que ya han entrado al ciclo.
Podemos, pues, escribir las cosas con un formato más acorde a estas observaciones:

Observemos que hemos escrito una suma infinita.
En realidad esta suma es finita, porque a partir del índice en adelante, todos los dígitos de son iguales a 0.
Luego, la escritura anterior es más compacta, y evita que tengamos que pensar cuántas cifras tiene .


Ejemplos de Aplicación a criterios conocidos de divisibilidad, y un par de casitos más

En todo lo que sigue, supondremos que , donde sólo una cantidad finita de las cifras es distinta de 0.

Divisibilidad por 2

Aquí tenemos para la fórmula (*), y que , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 2 si y sólo si la última cifra de es divisible por 2.

Divisibilidad por 3

Aquí tenemos para la fórmula (*), y que , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 3 si y sólo si la suma de las cifras de es múltiplo de 3.
Si al sumar las cifras de se obtiene un número grande, se le vuelven a sumar las cifras a este último número, y así sucesivamente hasta llegar a algo "pequeño" que ya nos permita decidir.

Divisibilidad por 4

Aquí tenemos para la fórmula (*), y que , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 4 si y sólo si la suma de su útlima cifra más el doble de su penúltima cifra es múltiplo de 4.

Divisibilidad por 5

Aquí tenemos para la fórmula (*), y que , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 5 si y sólo si la última cifra de es múltiplo de 5.

Divisibilidad por 6

Aquí tenemos para la fórmula (*), y que , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 6 si y sólo si la suma de última cifra más 4 veces la suma de las restantes cifras de es múltiplo de 6.

Este criterio es algo complicado. Se puede simplificar observando que 6 es el producto de 2 y 3.
Así que si la última cifra de es par, y la suma de las cifras de es múltiplo de 3, entonces es múltiplo de 6.

Divisibilidad por 7

Aquí tenemos para la fórmula (*), y que , , , , , , , y en general , para , siendo el sistema de restos de las potencias de 10 módulo 7. Se sigue que:



Esto da un criterio complicado de divisibilidad por 7, pero ciertamente funciona.

Divisibilidad por 8

Aquí tenemos para la fórmula (*), y que , ,  , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 8 si y sólo si la suma de su útlima cifra más el doble de su penúltima cifra más el cuádruple de su antepenúltima cifra es múltiplo de 8.

Divisibilidad por 9

Aquí tenemos para la fórmula (*), y que , y en general , para . Se sigue que:



Esto demuestra que  es divisible por 9 si y sólo si la suma de las cifras de es múltiplo de 9.

Divisibilidad por 10

Aquí tenemos para la fórmula (*), y que para . Se sigue que:



Esto demuestra que  es divisible por 10 si y sólo si la última cifra de es múltiplo de 10.
Pero esto sólo ocurre si la última cifra de es 0.

Divisibilidad por 11

Aquí tenemos para la fórmula (*), y que , , y luego estos restos se repiten cíclicamente.



donde .

Esto demuestra que  es divisible por 11 si y sólo si la suma de sus cifras pares más 10 veces la suma de sus cifras impares es múltiplo de 11.
Este criterio puede simplificarse un poco usando números negativos.
En efecto, observemos que . En ese caso, podemos tomar en la fórmula anterior, y obtenemos el conocido criterio que dice que es múltiplo de 11 si y sólo si lo es la suma de sus cifras pares menos la suma de sus cifras impares.

Divisibilidad por otros números

No lo voy a hacer, pero es de esperar que en la mayoría de los casos se obtengan criterios de divisibilidad complicados, similares al obtenido para la división por 7.






Base b.

Sea un entero positivo mayor que 1.
Dado un número entero positivo podemos representarlo en base , con los dígitos , de forma única, tal que la siguietne identidad se satisface:

Aquí, sólo una cantidad finta de cifras es distinta de 0.

Lo único que hay que cambiar en todo esto es la base 10 por la base , y el desarrollo matemática será el mismo.
Así, tendremos una fórmula como esta:

(*)                       

Aquí es el primer exponente tal que las potencias comienzan a repetir sus restos módulo .
Asimismo, es el sistema de restos de las potencias módulo .

Veamos un par de ejemplos.

Criterio de divisibilidad en base 2 de divisibilidad por 15.

Tenemos:







y a partir de aquí se repiten los restos módulo 15.
Así que tenemos y . También el sistema de restos es en este caso .
Aplicando la fórmula:

El criterio de divisibilidad no es muy simple de expresar verbalmente, pero parece fácil de aplicar en un cálculo.
Se debe separar las cifras binarias del número en 4 grupos, sumar los dígitos de cada grupo y multiplicar por la potencia adecuada de 2.
Si el resultado es múltiplo de 15, ya estamos...


Criterio de divisibilidad en base 27 de divisibilidad por 54.

Tenemos:





y a partir de aquí se repite lo mismo para las siguientes potencias.
El criterio de divisibilidad es muy simple. Se suma la primer cifra a 27 veces la suma de las restantes, y se verifica si el resultado es múltiplo de 54.


Que se diviertan dividiendo...

 

[argentinator]

Sección 5. Otras propiedades interesantes de divisibilidad y congruencias

(Esperando vuestras sugerencias...)

[argentinator]

Cuando esté con algo de tiempo voy a revisar lo que me sugerís, a ver si puedo cambiarlo sin demasiado esfuerzo...

[pepito]

Primero, una tontería nada más: en el teorema 3, me parece que sería mejor directamente enunciarlo para divisores enteros no nulos (no necesariamente positivos), porque si lo enunciás sólo para positivos y después extendés la definición de para divisores negativos, no te queda demostrado que se puede conseguir un cociente y un resto para todo par dividendo-divisor.

Después, una propiedad importante que yo agregaría es que .

[argentinator]

Primero, una tontería nada más: en el teorema 3, me parece que sería mejor directamente enunciarlo para divisores enteros no nulos (no necesariamente positivos), porque si lo enunciás sólo para positivos y después extendés la definición de para divisores negativos, no te queda demostrado que se puede conseguir un cociente y un resto para todo par dividendo-divisor.

Bien, mientras escribía, algunas cosas me parecieron mejor si me restringía a divisores positivos.
Creo que porque cuando d es negativo el resto... es no negativo, y queda menor que el valor absoluto de d.
Y después las congruencias se pueden poner algo confusas si d es negativo.

De todos modos es muy posible que cambie el enunciado según tu sugerencia.

[argentinator]

Digamos algo mas, y es que las potencias no pueden tener resto siempre distinto modulo , porque los restos posibles son, a lo sumo, . Así que en algún momento alguno de ellos tendrá que ser repetición de alguno de los anteriores. Más aún, debido a la conservación del producto por congruencias, las sucesivas potencias tendrán que repetirse con el mismo patrón, y de esa manera los restos modulo de las potencias de 10 que siguen se repetirán cíclicamente.

Para saber en con qué exponente se inicia el ciclo de repeticiones de restos, basta hallar el primer exponente entero positivo tal que .

Esto es falso por ejemplo d=7. Si d es primo con 10 se van a repetir cuando .

Es cierto, no lo demostré con cuidado, y me confié con lo que pasaba en algunos ejemplos.
Voy a tener que poner eso como una condición suficiente, pero no necesaria.

Saludos

[pepito]

Bien, mientras escribía, algunas cosas me parecieron mejor si me restringía a divisores positivos.
Creo que porque cuando d es negativo el resto... es no negativo, y queda menor que el valor absoluto de d.
Y después las congruencias se pueden poner algo confusas si d es negativo.

De todos modos es muy posible que cambie el enunciado según tu sugerencia.

Puede ser... la congruencia yo siempre la estudié con módulo positivo, pero el algoritmo de división, generalizado a todo , y lo que se pedía era justamente eso, que el resto sea estríctamente menor que el módulo del divisor.

Después, una propiedad de congruencias (no estoy 100% seguro de que no esté incluida):

.

Y después, si definís el mcm, estaría bueno incluir que

[argentinator]

Congruencias

Definición (congruencia). Sean números enteros cualesquiera, y sea un entero positivo. Se dice que son congruentes módulo si al aplicar el algoritmo de la división, el resto al dividir por es igual al resto de dividir por . Más precisamente, si , satisfacen , , entonces . En este caso se escribe la siguiente relación, llamada de congruencia módulo :

Creo que se puede simplificar si usas la definicion , al menos algunas de las propiedades las tienes gratis de usar las propiedades de la division (simetria, reflexividad, transitividad). Y lo mejor es que te ahorras todos los ~

Como sabemos, toda relación de equivalencia induce una partición del conjunto total en clases de equivalencia.
En este caso, para un entero positivo d, el conjunto de enteros queda particionado en clases de equivalencia, que son:

[/tex]

Te falto cerrar un [/tex]


--


Tal vez en el enunciado del TFA sea conveniente separar en dos partes: i) existencia de la factorizacion y ii) unicidad (salvo reordenamiento).

Ya arreglé estas cosas...
Además, justo tras la definición de congruencia agregué la definición que vos diste, que es la más usual, y así están ambas cosas juntas.
A mí también me gusta más tu definición, pero quería dejar resaltado quizás el papel del resto de la división en todo esto, y que de eso se trata la cuestión...

Lo engorroso del Teorema 2 lo arreglé poniendo las observaciones en spoiler.

Criterios de Divisibilidad

(...)

Para saber en con qué exponente se inicia el ciclo de repeticiones de restos, basta hallar el primer exponente entero positivo tal que .
El inicio de las repeticiones será ese exponente, o alguno de los anteriores, y en principio bastará hacer una búsqueda manual.
No voy a entrar en mayores detalles por ahora, quizá más adelante, si surge la inquietud en el público, se pueda ser más exacto.

Lo modifiqué así, espero que esté bien ahora (es una solución demasiado casera, pero bueno, todo es mejorable).

en el teorema 3, me parece que sería mejor directamente enunciarlo para divisores enteros no nulos (no necesariamente positivos), porque

Lo cambié a tu gusto

[argentinator]

Hola Topo, según tu útlima observación, creo que será mejor que directamente saque cualquier cosa relativa a las repeticiones.
Buscarlas a mano... y listo.
En algún momento empezarán.

[topo23]

Si de acuerdo.

[argentinator]

Bien, mientras escribía, algunas cosas me parecieron mejor si me restringía a divisores positivos.
Creo que porque cuando d es negativo el resto... es no negativo, y queda menor que el valor absoluto de d.
Y después las congruencias se pueden poner algo confusas si d es negativo.

De todos modos es muy posible que cambie el enunciado según tu sugerencia.

Puede ser... la congruencia yo siempre la estudié con módulo positivo, pero el algoritmo de división, generalizado a todo , y lo que se pedía era justamente eso, que el resto sea estríctamente menor que el módulo del divisor.

Después, una propiedad de congruencias (no estoy 100% seguro de que no esté incluida):

.

Y después, si definís el mcm, estaría bueno incluir que

Lo que he puesto es la implicación hacia un lado, para el míniimo común múltiplo.
Si los mcd son todos 1, entonces el mcm es el producto de los divisores, y daría la igualdad que pusiste.
No entiendo lo del "si y sólo si".
Creo que habrás querido poner que "si todos los mcd son 1, entonces (a congruente b (mod d_i), todo i, si y solo si a congruente con b módulo el producto).

Sería bueno poner eso explícitamente.

[argentinator]

Después, una propiedad de congruencias (no estoy 100% seguro de que no esté incluida):

.

La agregué como Teorema 6 en el post de Congruencias.
Parece cierta, pero no me acuerdo si es verdad... 
Confié en vos y por eso la escribí. ¿Estás seguro que es verdad? Fijate como la enuncié si es lo que vos decías.

Otra cosa pepito: debo decir que me agreda tu forma de escribir todo simbólicamente... pero el mundo exterior protesta cuando se hacen las cosas así.
Al escribir artículos, libros, o también respuestas en el foro, puede ser intimidante usar notación simbólica pura.
Aunque odio decirlo (porque va en contra de mis sentimientos) hay que buscar un equilibrio entre "palabrerío" y "chirimbolaje".

Saludos

[argentinator]

Muchachos, me tengo que ir.

Si tienen alguna otra sugerencia, díganme ahora... y si no será hasta mi próxima conexión...

[pepito]

Emmm... si, está mal escrito. Y ahora que veo la propiedad que pusiste, me parece que ni conviene agregar esta, porque la implicación en el otro sentido es obvia.

Lei mal. Ahora me tengo que ir, después subo la demostración bien.

[argentinator]

Bueno, pero la implicación para el otro lado no es tan obvia.

[pepito]

Tenés razón, me quedó medio mal escrito. Pero sí, lo que quise decir es exactamente eso. Para demostrarlo, conviene usar la propiedad/definición de congruencia y una propiedad de divisibilidad que convendría agregar (tal vez después de introducir el mcd) que dice que si entonces

Después, un par de cositas más que se podría agregar:

1) Aclarar en la identidad de Bezout que la combinación lineal no es única (una tontería nomás)

2) Un poco más importante, agregar que (y decir que en particular se puede tomar igual al cociente de la división entre y , dando lugar al algoritmo más básico (tal vez) para calcular el mcd, y que la información de los pasos sucesivos de este algoritmo sirve además para encontrar una combinación lineal de y igual a su mcd, de acuerdo con la identidad de Bezout).

[argentinator]

2) Un poco más importante, agregar que (y decir que en particular se puede tomar igual al cociente de la división entre y , dando lugar al algoritmo más básico (tal vez) para calcular el mcd, y que la información de los pasos sucesivos de este algoritmo sirve además para encontrar una combinación lineal de y igual a su mcd, de acuerdo con la identidad de Bezout).

Este es el Algoritmo de Euclides (o no?).

Se puede agregar, cómo no.