Congruencias

Sigamos con las 17 fichas y los paquetes de 5. Cada recuadro azul continuo contiene 5 fichas; el dorado discontinuo solo contiene las 2 restantes y aún no forma un paquete completo de 5.

El 5 indica el tamaño de cada grupo y en la división se llama divisor. El 3 o el 4 cuentan grupos completos y se llaman cociente. El 2 que queda se llama resto. El resto debe ser mayor o igual que 0 y menor que el tamaño del grupo. Si quedaran al menos 5, podríamos llenar otro paquete: todavía no habríamos terminado de agrupar.

Para describir distintos totales con una sola frase usamos letras. $a$ es un entero, uno de los números …, $-3$, $-2$, $-1$, 0, 1, 2, 3, …, sin parte decimal ni fraccionaria. $a \in \mathbb Z$ significa «$a$ es entero». $m$ es el tamaño fijo y entero positivo de cada grupo, aquí al menos 2. $q$ es el cociente entero y $r$ el resto:

Las dos letras juntas de $qm$ indican multiplicación, es decir, $q \times m$. Los números negativos no pueden representar directamente cantidades de paquetes reales, pero la recta numérica mantiene válida la misma igualdad: partimos de un múltiplo $qm$ que no supera $a$ y avanzamos $r$ unidades a la derecha hasta $a$. Por ejemplo, $-1 = (-1) \times 5 + 4$ significa avanzar 4 unidades a la derecha desde $-5$ hasta $-1$. El cociente es $-1$, pero el resto es 4, no $-1$.

La imagen ha encontrado restos para algunos enteros. Para construir reglas necesitamos dos cosas más: que todo entero pueda escribirse así y que no admita dos restos correctos diferentes. Demostraremos ambas por separado.

Primero, demostrar que todo entero se puede escribir

Si $a$ es mayor o igual que 0, empezamos en $a$ y restamos $m$ mientras lo que queda sea al menos $m$. Cada resta retira un grupo completo. El número disminuye al menos en 1 cada vez y no se vuelve negativo, así que el proceso termina: entre 0 y $a$ solo hay $a + 1$ enteros no negativos. Si hemos restado $q$ veces y llamamos $r$ al valor final, entonces $a = qm + r$ y $0 \le r < m$.

Si $a$ es negativo, escribimos $a = -n$ con $n$ positivo. Aplicamos el agrupamiento anterior a $n$ y obtenemos $n = qm + r$. Si $r = 0$, cambiar el signo de ambos miembros da $a = (-q)m + 0$. Si $r > 0$, el cambio de signo da $-qm - r$, pero $-r$ es negativo. Para obtener un resto no negativo, quitamos un $m$ de la parte de múltiplos completos y añadimos el mismo $m$ a la parte del resto:

Al desarrollar el miembro derecho obtenemos $-qm - m + m - r = -qm - r$, así que el valor no cambia. Como $0 < r < m$, al restar $r$ de $m$ se cumple $0 < m - r < m$, y el nuevo resto está dentro del intervalo permitido. Ambos casos cubren todos los enteros negativos, por lo que queda demostrada la existencia.

Después, descartar que haya dos respuestas distintas

Supongamos que alguien presenta dos escrituras, $a = qm + r$ y $a = sm + t$, con $r$ y $t$ entre 0 y $m - 1$. Restamos la segunda de la primera; como representan el mismo $a$, los miembros izquierdos se cancelan:

Como $r$ y $t$ están en ese intervalo, $t - r$ queda estrictamente entre $-m$ y $m$. Pero un múltiplo entero de $m$ es cero o tiene valor absoluto al menos $m$, porque todo entero no nulo tiene valor absoluto al menos 1. Por tanto, ese múltiplo solo puede ser cero. Así, $q - s = 0$, es decir, $q = s$; después, $t - r = 0$, es decir, $t = r$. Tanto el cociente como el resto dentro del intervalo son únicos.

Volvamos a 17 y 22. Su diferencia es $22 - 17 = 5$, exactamente un paquete. Añadir o quitar paquetes completos cambia el total, pero no el resto. Necesitamos una notación para esta coincidencia precisa: $a \equiv b \pmod{m}$, que se lee «$a$ es congruente con $b$ módulo $m$» y significa que ambos dejan el mismo resto al dividir entre $m$. El valor fijo $m$ se llama módulo.

Todos los enteros con el mismo resto forman una clase de restos. Cualquiera puede representar la clase completa y se llama representante. Por ejemplo, módulo 5, la clase de 2 contiene …, $-8$, $-3$, 2, 7, 12, 17, 22, …, porque cada uno es 5 por un entero más 2. Usar 2 como representante no significa que la clase solo contenga el entero 2.

Aquí $\equiv$ no significa igualdad entre enteros ni igualdad aproximada. Dice exactamente que tienen el mismo resto para el módulo indicado. No podemos olvidar ese módulo: 17 y 22 son congruentes módulo 5, pero al dividir entre 3 dejan restos 2 y 1.

Otra descripción facilita los cálculos. $m \mid n$ significa «$m$ divide a $n$», es decir, que $n$ es $m$ multiplicado por un entero; la barra vertical no es un signo de división. Demostraremos en ambos sentidos que tener el mismo resto equivale exactamente a que la diferencia sea múltiplo de $m$.

Supongamos primero que los restos son iguales y escribamos $a = qm + r$ y $b = sm + r$. Al restar, $a - b = qm + r - sm - r = m(q - s)$. Como $q - s$ sigue siendo entero, la diferencia es un múltiplo entero de $m$.

A la inversa, supongamos $a - b = mk$ con $k$ entero. Sin suponer que los restos coinciden, escribimos $a = qm + r$ y $b = sm + t$. Sustituimos y pasamos al otro miembro la parte que ya es múltiplo de $m$:

$r - t$ está estrictamente entre $-m$ y $m$ y es a la vez múltiplo de $m$. El argumento de unicidad anterior obliga a que sea cero, así que $r = t$. Hemos demostrado ambos sentidos. La doble flecha significa que cualquiera de las dos afirmaciones implica la otra.

También podemos justificar directamente tres operaciones pequeñas. Todo número es congruente consigo mismo porque $a - a = m \times 0$. Podemos intercambiar los miembros de una congruencia porque $a - b = mk$ implica $b - a = m(-k)$. Con el mismo módulo podemos encadenar dos relaciones: si $a - b = mk$ y $b - c = mh$, al sumar obtenemos $a - c = m(k + h)$. Así, si $a$ es congruente con $b$ y $b$ con $c$, entonces $a$ es congruente con $c$; el módulo debe ser siempre el mismo.

Si solo conocemos los restos, ¿podemos sumar o multiplicar? Supongamos $a \equiv b \pmod{m}$ y $c \equiv d \pmod{m}$. La descripción mediante diferencias permite escribir $a = b + mk$ y $c = d + mh$, con $k$ y $h$ enteros. Estas igualdades dicen exactamente qué hemos omitido: varios grupos completos de $m$.

Suma y resta

$k + h$ y $k - h$ son enteros, así que las diferencias calculadas en ambas líneas son múltiplos de $m$. Según la caracterización ya demostrada, $a + c \equiv b + d \pmod{m}$ y $a - c \equiv b - d \pmod{m}$. En particular, podemos sumar el mismo entero a ambos miembros, porque todo entero es congruente consigo mismo.

Multiplicación

Al multiplicar debemos incluir todos los términos, también el producto de los dos múltiplos omitidos. Tras desarrollar los paréntesis, todos los términos que contienen $m$ se agrupan en un múltiplo de $m$:

Dentro del paréntesis solo hay sumas y productos de enteros, así que sigue siendo entero. Por tanto, $ac \equiv bd \pmod{m}$. Esto explica por qué podemos sustituir primero los factores por sus restos. Por ejemplo, módulo 5, $17 = 3 \times 5 + 2$, de modo que $17 \equiv 2$; y $22 = 4 \times 5 + 2$, de modo que $22 \equiv 2$. Así, $17 \times 22 \equiv 2 \times 2 = 4 \pmod{5}$. Comprobamos con el producto completo: $374 = 74 \times 5 + 4$. El cálculo más pequeño conserva exactamente el resto que buscamos.

Potencias de exponente entero positivo

En $a^{n}$, si $n$ es un entero positivo, significa multiplicar $n$ factores iguales a $a$. Si $a$ y $b$ son congruentes, la regla del producto da primero la congruencia de $a^{2}$ y $b^{2}$. Al multiplicar después $a^{2} \equiv b^{2}$ por $a \equiv b$, obtenemos $a^{3} \equiv b^{3}$. ¿Por qué esto cubre todo entero positivo $n$ y no solo dos ejemplos? El caso inicial $n = 1$ es la congruencia conocida. Si el paso $n$ es válido, multiplicarlo por $a \equiv b$ demuestra el paso $n + 1$. Partiendo de 1 y repitiendo, llegamos a cualquier entero positivo $n$. Este razonamiento, «el inicio es válido y cada paso implica el siguiente», se llama demostración por inducción.

Considera $2x \equiv 2 \pmod{6}$. La igualdad ordinaria $2x = 2$ solo tiene $x = 1$. Pero ahora pedimos algo distinto: que $2x - 2$ sea múltiplo de 6. Tanto $x = 1$ como $x = 4$ sirven, porque $2 \times 1 - 2 = 0 = 6 \times 0$ y $2 \times 4 - 2 = 6 = 6 \times 1$. Sin embargo, 1 y 4 no son congruentes módulo 6, pues $4 - 1 = 3$ no es múltiplo de 6.

En la tabla inicial, los restos 1 y 4 se convierten ambos en 2 al multiplicarlos por 2 módulo 6. Una vez unidos ambos puntos de partida, el resultado no permite saber de cuál veníamos. Cancelar sin justificación pierde precisamente esa información.

En una igualdad auténtica sí podemos dividir. Escribimos $2x - 2 = 6k$ con $k$ entero. Dividimos cada término entre 2 y obtenemos $x - 1 = 3k$. Esto dice $x \equiv 1 \pmod{3}$: el módulo ha cambiado a 3. Invirtiendo los pasos, cualquier $x$ escrito así cumple la condición. Por tanto, todas las soluciones enteras son $x = 1 + 3k$, es decir, …, $-5$, $-2$, 1, 4, 7, 10, …. Al cancelar el factor, también cambió el módulo.

¿Cuándo podemos mantener el módulo original? Si no podemos, ¿cómo debemos cambiarlo? Para responder por completo necesitamos una herramienta: formar 1, o un divisor común mayor, mediante combinaciones de múltiplos enteros. Vamos a demostrar que existe, en lugar de darlo por supuesto.

Tomemos enteros positivos $A$ y $M$. Un entero positivo que divide a ambos es un divisor común positivo. Siempre existe al menos el 1 y solo hay un número finito de ellos: si $A = gh$ y $g$ y $h$ son positivos, entonces $h \ge 1$, por lo que $g \le A$. Así, todo divisor positivo pertenece a la lista finita 1, 2, …, $A$. El mayor se llama máximo común divisor y se escribe $\gcd (A, M)$. No solo queremos encontrarlo, sino demostrar que puede expresarse como una combinación de múltiplos enteros $uA + vM$.

Sustituir un par sin cambiar sus divisores comunes

Dividimos $A$ entre $M$ y escribimos $A = qM + r$. Si el entero positivo $g$ divide a $A$ y $M$, podemos escribir $A = gu$ y $M = gv$. Entonces $r = A - qM = gu - qgv = g(u - qv)$, por lo que $g$ también divide a $r$. A la inversa, si $M = gv$ y $r = gw$, entonces $A = qM + r = qgv + gw = g(qv + w)$, así que $g$ también divide a $A$. Por tanto, los pares $(A, M)$ y $(M, r)$ tienen exactamente los mismos divisores comunes positivos.

Mientras el resto no sea cero, seguimos sustituyendo así. Cada nuevo resto es un entero no negativo menor que el divisor anterior, por lo que los restos positivos no pueden disminuir indefinidamente. Finalmente llegamos a $(d, 0)$. Todo divisor positivo de $d$ también divide a 0, porque 0 es ese divisor multiplicado por 0; por tanto, el máximo común divisor del último par es el propio $d$. Cada sustitución conserva todos los divisores comunes, así que $d$ también es el máximo común divisor de los valores originales $A$ y $M$. Este procedimiento se llama algoritmo de Euclides.

Dejar constancia de cómo se obtuvo cada resto

Al inicio, $A = 1A + 0M$ y $M = 0A + 1M$ ya son combinaciones de múltiplos enteros de $A$ y $M$. Supongamos que los dos números actuales se escriben $uA + vM$ y $sA + tM$. Restar al primero $q$ veces el segundo da $(u - qs)A + (v - qt)M$, cuyos coeficientes siguen siendo enteros. Así, cada nuevo resto también es una combinación de ese tipo. La propiedad vale al inicio y se conserva en cada paso, de modo que el último número no nulo $d$ también admite esa expresión, incluso si es uno de los números iniciales:

Esta igualdad se llama identidad de Bézout. $u$ y $v$ pueden ser negativos: una combinación de múltiplos enteros admite tanto sumas como restas. Hemos demostrado que los coeficientes existen, sin suponer que siempre podamos adivinarlos.

Haz los números: combina 7 y 12 para obtener 1

Para 7 y 12, empezamos dividiendo el mayor entre el menor. Después, cada fila usa el divisor y el resto de la anterior:

El último resto no nulo es 1, así que $\gcd (7, 12) = 1$. ¿Cómo escribimos ese 1 con los números iniciales 7 y 12? La igualdad $1 = 5 - 2 \times 2$ muestra de dónde procede. Sustituimos el 2 por $7 - 5$ y el 5 restante por $12 - 7$; así solo quedan 7 y 12. Conservamos también todos los pasos del desarrollo:

Comprobemos: $36 - 35 = 1$. No hemos dividido entre 7; hemos encontrado un multiplicador entero $-5$ que hace que el producto difiera de 1 en un múltiplo de 12. Ese es precisamente el método que buscábamos para sustituir la división.

Consideremos primero el caso en que el multiplicador $c$ y el módulo $m$ tienen máximo común divisor 1. Dos enteros positivos así se llaman coprimos: su único divisor común positivo es 1. Bézout da enteros $u$ y $v$ tales que $uc + vm = 1$. Supongamos $cA \equiv cB \pmod{m}$, es decir, $c(A - B) = mk$. Multiplicamos ahora la identidad de Bézout por $A - B$:

El paréntesis es entero, así que $m$ divide a $A - B$, es decir, $A \equiv B \pmod{m}$. Elegimos Bézout para convertir un miembro en $A - B$ y aprovechar en el otro $c(A - B)$, que ya sabemos múltiplo de $m$. Hemos demostrado que, si el multiplicador y el módulo son coprimos, podemos cancelar el multiplicador conservando el módulo.

¿Qué cambia exactamente cuando hay un divisor común?

Sea $d = \gcd (c, m)$, con $c$ entero positivo. Dividimos ambos entre $d$ y escribimos $c' = c/d$ y $m' = m/d$, que siguen siendo enteros. Son coprimos: si un entero positivo $h$ divide a $c'$ y $m'$, entonces $dh$ divide a $c$ y $m$. Como $d$ ya es el máximo común divisor, $dh \le d$; al dividir entre el positivo $d$, obtenemos $h \le 1$. Por tanto, $h$ solo puede ser 1.

Demostremos primero el sentido hacia la derecha. Escribimos $c(A - B) = mk$ y dividimos la igualdad entre $d$ para obtener $c'(A - B) = m'k$. Como $c'$ y $m'$ son coprimos, la demostración anterior implica que $m'$ divide a $A - B$. A la inversa, si $A - B = m'j$ con $j$ entero, multiplicar por $c = dc'$ da $c(A - B) = dc'm'j = mc'j$, un múltiplo de $m$, así que se cumple la congruencia original. Ambos sentidos quedan demostrados.

Debemos aclarar un caso límite. Si $m/d = 1$, el resto al dividir entre 1 siempre es 0, porque cualquier entero $n$ cumple $n = n \times 1 + 0$. Por tanto, todos los enteros son congruentes módulo 1 y la condición simplificada no impone ninguna restricción. La demostración sigue siendo válida porque 1 divide a todo entero. Empezamos con $m \ge 2$, pero este caso puede aparecer después de cancelar.

Deshacer una multiplicación con otra multiplicación

En aritmética ordinaria, multiplicar por $1/c$ deshace multiplicar por $c$. Aquí buscamos un entero $u$ tal que $cu \equiv 1 \pmod{m}$. Ese $u$ se llama inverso multiplicativo de $c$ módulo $m$. Es un entero que invierte la operación en la relación de restos, no la fracción ordinaria $1/c$. Si $cx \equiv b$, al multiplicar ambos miembros por $u$ obtenemos $ucx \equiv ub$; después, $uc \equiv 1$ y la regla del producto dan $x \equiv ub$.

El inverso existe exactamente cuando $\gcd (c, m) = 1$. Si el máximo común divisor es 1, Bézout da $uc + vm = 1$, por lo que $uc - 1 = -vm$ y queda demostrado $uc \equiv 1$. A la inversa, si $uc \equiv 1$, tenemos $uc - 1 = mk$, es decir, $1 = uc - mk$. Todo divisor común positivo de $c$ y $m$ divide esta combinación y, por tanto, divide a 1. Si $1 = gh$, con $g$ y $h$ positivos, $h \ge 1$ obliga a $g \le 1$; así, el único divisor positivo de 1 es 1 y el máximo común divisor también es 1. Hemos demostrado tanto la existencia bajo esa condición como su necesidad.

La igualdad anterior $1 = 3 \times 12 - 5 \times 7$ muestra que $-5$ es un inverso de 7 módulo 12. Sumando 12 obtenemos el representante 7. Comprobamos: $7 \times 7 = 49 = 4 \times 12 + 1$. El inverso no es un entero único, porque añadir múltiplos del módulo conserva la propiedad, pero su resto sí es único. Si $cu \equiv cv \equiv 1$ y $\gcd (c, m) = 1$, la regla de cancelación demostrada da $u \equiv v \pmod{m}$.

Ahora podemos resolver $ax \equiv b \pmod{m}$: $a$ es un entero positivo, $b$ un entero cualquiera, $m \ge 2$, y $x$ el entero buscado. «Lineal» significa que $x$ solo se multiplica por un coeficiente $a$, sin cuadrados ni potencias superiores. Queremos responder tres preguntas: ¿hay soluciones?, ¿cómo encontramos una?, ¿cómo sabemos que las hemos encontrado todas?

Primero decide si puede haber solución

Escribimos $d = \gcd (a, m)$. Si $x$ es solución, existe un entero $k$ tal que $ax - b = mk$. Reordenando, $b = ax - mk$. Sustituyendo $a = d(a/d)$ y $m = d(m/d)$, obtenemos $b = d((a/d)x - (m/d)k)$. Todo el paréntesis es entero, así que $d$ debe dividir a $b$. Por ejemplo, $6x \equiv 4 \pmod{9}$ es imposible: todo $6x - 9k$ es múltiplo de 3, pero $4 = 1 \times 3 + 1$ no lo es.

Supongamos ahora que $d$ sí divide a $b$ y escribamos $b = dh$ con $h$ entero. Bézout da $ua + vm = d$. Multiplicamos toda la igualdad por $h$: $a(uh) + m(vh) = dh = b$. Reordenando, $a(uh) - b = -m(vh)$. Por tanto, $x_{0} = uh$ es una solución, porque su producto por $a$ difiere de $b$ en un múltiplo de $m$. Queda demostrado en ambos sentidos el criterio de existencia:

Después halla todas las soluciones, sin omitir ni añadir ninguna

Sea $x_{0}$ una solución conocida y $x$ cualquier otra. Restamos $ax_{0} \equiv b$ de $ax \equiv b$; la regla de resta da $a(x - x_{0}) \equiv 0 \pmod{m}$. Aplicando la cancelación correcta ya demostrada, con $d = \gcd (a, m)$, obtenemos $x - x_{0} \equiv 0 \pmod{m/d}$. Esto significa $x - x_{0} = (m/d)t$ con $t$ entero. Por tanto, toda solución debe tener esta forma:

Aún no podemos terminar: debemos comprobar que todo entero de esa forma cumple la condición. Al sustituir obtenemos $ax - b = a(x_{0} + (m/d)t) - b = (ax_{0} - b) + m(a/d)t$. El primer término es múltiplo de $m$ porque $x_{0}$ ya es solución; el segundo también, porque $a/d$ y $t$ son enteros. Su suma sigue siendo múltiplo de $m$. La fórmula da todas las soluciones y no incluye ninguna falsa.

¿Por qué hay exactamente $d$ clases de solución módulo $m$?

Hay infinitas soluciones enteras, pero no infinitos restos al dividir entre $m$. Tomando $t = 0$, 1, …, $d - 1$ en la fórmula, obtenemos $d$ clases de restos distintas. ¿Por qué distintas? Si las soluciones de $t = i$ y $t = j$ fueran congruentes módulo $m$, su diferencia $(m/d)(i - j)$ sería $mk$. Dividimos esa igualdad entre el positivo $m/d$ y obtenemos $i - j = dk$. Pero $-d < i - j < d$, así que el argumento de unicidad obliga a $i = j$.

Estas clases también incluyen los demás enteros $t$. Dividimos $t$ entre $d$ y escribimos $t = dq + j$ con $0 \le j < d$; si $d = 1$, el resto es 0. Entonces $x_{0} + (m/d)t = x_{0} + (m/d)j + mq$. El término final $mq$ no cambia el resto módulo $m$, así que ya pertenece a la clase representada por $j$. Siempre que haya soluciones, hay exactamente $d$ clases.

Un ejemplo completo: $4x \equiv 2 \pmod{6}$

$6 = 1 \times 4 + 2$ y $4 = 2 \times 2 + 0$ dan $d = 2$. Como 2 divide al 2 del miembro derecho, hay solución. Sustituyendo hacia atrás, $2 = 6 - 4 = (-1) \times 4 + 1 \times 6$. Aquí $h = b/d = 2/2 = 1$, así que $x_{0} = (-1) \times 1 = -1$ es una solución. El intervalo es $m/d = 6/2 = 3$ y todas las soluciones son $x = -1 + 3t$.

También podemos escribir esta sucesión empezando por 2, porque $-1 + 3t = 2 + 3(t - 1)$ y $t - 1$ sigue recorriendo todos los enteros. En la forma $x = 2 + 3k$ se ven fácilmente los dos representantes módulo 6: 2 y 5. Sustituir directamente comprueba toda la familia, no solo esos dos números:

Cualquier entero $k$ hace que esta expresión sea múltiplo de 6. A la inversa, ya demostramos que toda solución tiene esta forma. Una respuesta completa requiere comprobar ambos sentidos.

Volvamos al enorme producto inicial. La última cifra $r$ de un entero decimal no negativo $N$ está entre 0 y 9. Las cifras anteriores cuentan decenas completas, así que $N = 10q + r$. Por tanto, la última cifra es exactamente el resto al dividir entre 10. Buscamos el resto de $7^{2026}$, no el número enorme completo.

Escribir cuatro filas no demuestra que el patrón se repita siempre. Se repite por la regla de multiplicación: multiplicar cualquier $7^{n}$ por $7^{4}$ equivale a multiplicar su resto por 1, de modo que $7^{n+4} \equiv 7^{n} \pmod{10}$. Aquí $7^{n+4} = 7^{n} \times 7^{4}$ consiste en unir $n$ factores 7 con otros 4 factores 7.

Dividimos ahora la cantidad de factores entre 4: $2026 = 4 \times 506 + 2$. Los 2026 factores forman 506 bloques de 4 y sobran 2 factores. Cada bloque tiene resto 1 y los dos factores finales tienen producto de resto 9, así que:

La última cifra es 9. Observa que agrupamos el exponente según la longitud de ciclo 4 ya demostrada; no sustituimos 2026 por su resto al dividir entre 10. El módulo usado para los valores y la longitud del ciclo son cosas distintas.

¿Por qué funciona la prueba de la suma de dígitos para la divisibilidad entre 9?

Un número de cuatro cifras $a$, $b$, $c$ y $d$ representa $N = 1000a + 100b + 10c + d$. Ese es el valor posicional decimal: $a$ cuenta millares, $b$ centenas, $c$ decenas y $d$ unidades. Como $10 = 1 \times 9 + 1$, tenemos $10 \equiv 1 \pmod{9}$. La regla de potencias da $100 = 10^{2} \equiv 1^{2} = 1$ y $1000 = 10^{3} \equiv 1^{3} = 1$. Aplicamos después las reglas de producto y suma:

Lo mismo vale con más o menos cifras: el peso de cada posición adicional es una potencia entera positiva de 10 cuyo resto sigue siendo 1; el de las unidades ya es 1. Repetir la regla de suma demuestra el resultado para cualquier número finito de cifras. Ser divisible entre 9 equivale a tener resto 0, así que un número es divisible entre 9 si y solo si lo es la suma de sus cifras.

Para 2349, la suma de cifras es $2 + 3 + 4 + 9 = 18 = 2 \times 9$ y el resto es 0; la división directa confirma $2349 = 261 \times 9$. Para 2026, la suma es $2 + 0 + 2 + 6 = 10 = 1 \times 9 + 1$ y el resto es 1; comprobamos $2026 = 225 \times 9 + 1$. Ahora la regla tiene una justificación y no solo responde si hay divisibilidad, sino que da el resto.

Las congruencias también pueden demostrar que una ecuación entera no tiene solución. Considera $x^{2} = 4y + 2$ con $x$ y $y$ enteros. En lugar de probar números sin fin, preguntamos qué restos módulo 4 puede tener cada miembro. Todo entero $x$ pertenece exactamente a uno de los restos 0, 1, 2 o 3. Si $x \equiv r \pmod{4}$, la regla del producto da $x^{2} \equiv r^{2}$. Por tanto, estos cuatro casos cubren todos los enteros:

Así, el cuadrado de un entero solo puede dejar resto 0 o 1 módulo 4, nunca 2. El miembro derecho $4y + 2$ siempre deja 2, incluso si $y$ es negativo, porque $y$ es un cociente entero y $0 \le 2 < 4$. Dos enteros iguales deben tener el mismo resto único, pero aquí los restos no pueden coincidir. No existe, por tanto, ninguna pareja entera $(x, y)$ que satisfaga la ecuación.