El teorema chino del resto: hacer coincidir dos registros de restos

Primero se toman $8$ discos. Al hacer grupos de $3$, se completan $2$ grupos y sobran $2$ discos. Cada grupo lleno tiene $3\times2=6$ discos; si se añaden los $2$ que sobran, se vuelve a los $8$ originales. La cantidad que sobra se llama resto.

¿Por qué el resto tiene que ser menor que la cantidad de cada grupo? Si sobraran $3$ discos, se podría completar otro grupo y no podríamos decir que el reparto ha terminado. Por eso, el resto de dividir entre $3$ solo puede ser $0,1,2$. Cuando el resto es $0$, significa que el reparto fue exacto.

Abajo, cada recuadro de línea continua es un grupo completo y los de línea discontinua son los discos que sobran. Cambia el total y luego cambia la cantidad de cada grupo de $3$ a $5$; el total no cambia por cambiar la forma de agrupar. Los discos verdes están en los grupos completos y los dorados son el resto.

Ahora representamos con $x$ el entero que buscamos y con $q$ el número de grupos completos. «Dividir entre $3$ y que sobre $2$» se escribe $x=3q+2$. Como solo estudiamos cantidades de discos enteros, aquí $x$ y $q$ son enteros.

El primer registro pide que el total, dividido entre $3$, deje $2$. Empezando en $2$ y sumando cada vez un grupo completo de $3$, el resto no cambia, así que se obtienen $2,5,8,11,14,17,\ldots$. Todos estos números cumplen el primer registro; ningún otro número no negativo lo cumple, porque al quitar los dos que sobran debe quedar exactamente un número entero de grupos de $3$.

El segundo registro pide que al dividir entre $5$ sobre $3$. Del mismo modo, empezando en $3$ y sumando $5$ cada vez, se obtiene $3,8,13,18,23,\ldots$. Buscamos los números que aparecen en las dos columnas a la vez, no la suma directa de los dos restos.

Abajo se revisa cada vez un total candidato de la primera columna y se agrupa el mismo número en grupos de $5$. Los números alineados en las dos filas representan el mismo total; una marca rellena indica que se cumple la condición de esa fila. Los candidatos se revisan en el orden $2$, $5$, $8$.

Una vez encontrado el $8$, volvemos a los dos registros para comprobarlo: $8=3\times2+2$ y también $8=5\times1+3$. Por tanto, el $8$ cumple de verdad. Pero, ¿habrá otras respuestas? A continuación explicamos cómo cubrir todas las posibilidades.

Sumar $15$ a cualquier total equivale a añadir $5$ grupos de $3$ y también $3$ grupos de $5$, porque $15=3\times5=5\times3$. Las dos formas de repartir solo añaden grupos completos, y el resto no cambia. Restar $15$ también conserva el resto.

Todo entero se puede dividir entre $15$ y escribir como $x=15t+r$, con $0\le r<15$. Aquí $t$ es un entero y $r$ es el resto. Por ejemplo, $23=15\times1+8$, y también $-7=15\times(-1)+8$. Por tanto, a todo entero se le pueden sumar o restar varios $15$ para llegar a un número entre $0$ y $14$.

Por eso, basta con revisar de $0$ a $14$ para no perder ninguna clase de respuesta. De ellos, solo $2,5,8,11,14$ cumplen el primer registro; sus restos al dividir entre $5$ son, en orden, $2,0,3,1,4$, y solo el $8$ deja resto $3$. Esto da todas las soluciones enteras: $x=8+15t$, donde $t$ puede ser cualquier entero.

Si volvemos al problema del total de discos, el total no puede ser negativo, así que solo quedan $8,23,38,\ldots$. Si la pregunta es solo sobre enteros, $\ldots,-22,-7,8,23,38,\ldots$ pertenecen todos a la misma familia de respuestas.

Para escribir los registros de restos de forma más breve, introducimos la notación $x\equiv2\pmod3$, que se lee «$x$ es congruente con $2$ módulo $3$». Aquí significa exactamente que al dividir entre $3$ el resto es $2$, es decir, que $x-2$ es múltiplo entero de $3$. El «módulo» es el $3$ que se usa para agrupar en este caso.

Ya hemos resuelto por completo el ejemplo con $3$ y $5$. Pero, al cambiarlos por otros dos números, ¿por qué a veces siempre se encuentra una respuesta y a veces no? Necesitamos saber si los dos tipos de grupos completos tienen un tamaño común.

Si un entero positivo divide a dos números, se llama divisor común de ambos. Es decir, cada uno de los dos números es igual a ese entero multiplicado por algún entero, sin resto. El mayor de ellos se llama máximo común divisor y se escribe $\gcd(m,n)$. Por ejemplo, los divisores comunes de $4$ y $6$ son $1,2$, y el mayor es $2$; $3$ y $5$ solo tienen el divisor común $1$, y en ese caso se dice que son coprimos.

¿Cómo se encuentra el máximo común divisor y cómo se relaciona con los dos números originales? Primero se hace la división con resto $a=bq+r$. Si un número divide a $a,b$, también divide a $r=a-bq$. A la inversa, si divide a $b,r$, también divide a $a=bq+r$. Por eso, los divisores comunes de $(a,b)$ y de $(b,r)$ son exactamente los mismos.

Podemos ir sustituyendo el par mayor por «el divisor y el resto». El resto positivo se hace estrictamente más pequeño cada vez, así que al final se llega necesariamente al resto $0$. Todo entero positivo divide a $0$, de modo que el máximo común divisor del último par es el número distinto de cero que queda; puede ser el resto del paso anterior o el divisor inicial. Por ejemplo, $6=2\times3+0$: el último par es $(3,0)$ y la respuesta es $3$. Cada sustitución conserva los divisores comunes, así que ese número distinto de cero es también el máximo común divisor de los dos números originales. Este procedimiento se llama algoritmo de Euclides.

Abajo se conservan los dos números originales, $3$ y $5$, y cada nuevo resto se escribe como «un número original multiplicado por un entero, más otro término». La primera fila es solo $3=0\times5+3$; así también se puede empezar por el número menor, y cada paso posterior sigue siendo válido.

Ahora aplicamos esta herramienta a dos módulos positivos coprimos cualesquiera, $m,n$. Su máximo común divisor es $1$, así que, tras aplicar el algoritmo de Euclides y sustituir hacia atrás, se encuentran enteros $u,v$ tales que $um+vn=1$. Aquí $u,v$ son los dos coeficientes de una combinación como la anterior y pueden ser negativos.

Queremos un entero $x$ que deje resto $a$ al dividir entre $m$ y resto $b$ al dividir entre $n$, con $0\le a<m$ y $0\le b<n$. Primero aseguramos la primera condición: sea $x=a+mk$, donde el entero $k$ todavía no está decidido. Así, elijamos como elijamos $k$, $x-a$ es múltiplo entero de $m$.

La segunda condición exige que $x-b=a-b+mk$ sea múltiplo entero de $n$. Por eso queremos que la diferencia entre $mk$ y $b-a$ sea divisible entre $n$. Si multiplicamos la igualdad conocida $um+vn=1$ por $b-a$, podemos construir esa diferencia:

Ahora elegimos $k=u(b-a)$. Al sustituir en la línea anterior se obtiene $mk-(b-a)=-nv(b-a)$, y el lado derecho es múltiplo entero de $n$. Por tanto, $x=a+mu(b-a)$ cumple los dos registros a la vez. Esto demuestra que la respuesta existe siempre, y no solo que hayamos enumerado algunos casos exitosos.

A continuación vemos en cuántas clases pueden repartirse las respuestas. Si $x,y$ cumplen ambos registros, entonces $x-y$ es múltiplo entero de $m$ y de $n$. Escribimos primero $x-y=mt$. Sabemos que $mt$ es divisible entre $n$, y queremos demostrar que $t$ también lo es; no podemos simplemente tachar $m$.

Volvemos a usar $um+vn=1$; multiplicando ambos lados por $t$ se obtiene $t=u(mt)+v(nt)$. El primer término es múltiplo entero de $n$, porque $mt$ lo es; el segundo también, porque tiene a $n$ como factor. La suma de ambos sigue siendo múltiplo entero de $n$, así que $t=ns$ con $s$ entero. Por tanto, $x-y=mns$.

Por tanto, dos respuestas cualesquiera difieren en un múltiplo entero de $mn$; a la inversa, sumar un múltiplo entero de $mn$ a una respuesta no cambia ningún resto. Si dividimos la respuesta encontrada entre $mn$ y tomamos el resto $r$, obtenemos la única respuesta del intervalo $0\le r<mn$; todas las respuestas son $x=r+mn s$. Este es el teorema chino del resto para dos módulos coprimos.

¿Qué ocurre si los módulos no son coprimos? Por ejemplo, los números que dejan resto $1$ al dividir entre $4$ son todos impares, y los que dejan resto $2$ al dividir entre $6$ son todos pares. Un mismo entero no puede ser impar y par a la vez, así que estos dos registros se contradicen. El factor común $2$ es justo donde nace el conflicto.

Sea $d$ el máximo común divisor de los dos módulos. Si hay una respuesta común, se escribe $x=a+mk=b+nl$. Al pasar los términos de lado se obtiene $b-a=mk-nl$. Como $d$ divide a $m,n$, cada término de la derecha es múltiplo entero de $d$, así que $b-a$ debe ser divisible entre $d$. Esta es una condición necesaria.

Esta condición también es suficiente. El algoritmo de Euclides da $um+vn=d$. Si $b-a=dc$, multiplicando ambos lados por el entero $c$ se obtiene $muc+nvc=b-a$. Tomando $x=a+muc$, se diferencia de $a$ en un múltiplo entero de $m$ y de $b$ en $-nvc$, que también es múltiplo entero de $n$; por eso cumple las dos condiciones.

Por último, encontramos el intervalo exacto de repetición. Sacando el factor común, escribimos $m=dM$ y $n=dN$. $M,N$ deben ser coprimos: si tuvieran un factor común $h$ mayor que $1$, los $m,n$ originales tendrían un factor común mayor $dh$, lo que contradice que $d$ sea el máximo común divisor.

La diferencia de dos respuestas es múltiplo de $m$, así que se escribe $dMt$; también es múltiplo de $n=dN$, por lo que $Mt$ es múltiplo de $N$. Como $M,N$ son coprimos, la razón de cancelación demostrada en el capítulo anterior implica que $t$ es múltiplo de $N$. Por tanto, la diferencia de dos respuestas es siempre múltiplo de $dMN=mn/d$.

$dMN$ es a la vez múltiplo de $m=dM$ y de $n=dN$, y el razonamiento anterior muestra que cualquier múltiplo común tiene que ser múltiplo de él. Por tanto, es el mínimo común múltiplo y se escribe $\operatorname{lcm}(m,n)$. Cuando hay solución, todas las soluciones se repiten cada este número.

Abajo puedes cambiar los módulos y los restos. Que la diferencia de los dos restos sea divisible entre el máximo común divisor decide si puede haber solución. También puedes revisar los candidatos uno a uno y comprobar este criterio. La tabla enumera todos los candidatos que cumplen el primer registro dentro de un intervalo completo de repetición, así que al recorrerla termina la comprobación de este grupo de condiciones.

Al combinar dos registros se obtiene otro registro de restos. Por ejemplo, el $x=8+15t$ de antes puede escribirse como $x\equiv8\pmod{15}$. Si además se pide que al dividir entre $7$ sobre $2$, emparejamos el nuevo registro con este registro ya combinado.

Primero miramos $8,23,38,53,68,83,98$; sus restos al dividir entre $7$ son, en orden, $1,2,3,4,5,6,0$, así que esta vez se elige $23$. Como $15$ y $7$ son coprimos, el nuevo intervalo de repetición es $15\times7=105$ y se obtiene $x=23+105s$. Comprobamos los tres registros originales: $23=3\times7+2$, $23=5\times4+3$, $23=7\times3+2$.

Con más registros, podemos repetir este proceso de combinación. En cada paso se comprueba primero la condición del máximo común divisor de los dos módulos actuales; si no son compatibles, no existe ningún entero que cumpla todos los registros a la vez. Si son compatibles, el registro combinado conserva todas las condiciones anteriores y basta con añadir el siguiente.

Si los módulos iniciales son coprimos dos a dos, cada combinación conserva esa propiedad. La razón se ve con la regla de cancelación ya demostrada: si un número $p$ es coprimo con $m$ y con $n$, se pueden escribir $um+vp=1$ y $rn+sp=1$; al multiplicarlos se obtiene $1=urmn+p(ums+vrn+vsp)$, así que cualquier divisor común de $mn$ y $p$ tiene que dividir a $1$. Usándolo repetidamente se obtiene el teorema chino del resto para más módulos coprimos.