A continuación se presentan algunas propiedades interesantes de la adición modular:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a + b + c) mod m = ((a mod m) + (b mod m) + (c mod m )) modelo m
Ejemplo 1:
Hallar el resto de 22 + 26 + 29 al dividir por 5.
Solución:
Al dividir 22 por 5 nos queda 2 de resto.
Al dividir 26 por 5 nos queda 1 como resto.
Al dividir 29 por 5 nos queda 4 como resto.
El resto de la expresión (22 + 26 + 29)/5 será igual a (2 + 1 + 4)/5.
El resto combinado será igual al resto de 7/5, es decir, 2.
Ejemplo 2:
Hallar el resto de 1234 + 5678 + 1478 al dividir por 11.
Solución:
Al dividir 1234 por 11 nos queda 2 de resto.
Al dividir 5678 por 11 nos queda 2 como resto.
Al dividir 1478 por 11 nos queda 4 como resto.
Rem [(1234 + 5678 + 1478)/11] = Rem [(2 + 2 + 4)/11]
Rem [8/11] = 8.
¿Cómo es útil?
Si necesitamos encontrar el resto de la suma de dos números grandes, podemos evitar hacer la suma de números grandes, especialmente útil en la programación donde la suma de números grandes puede causar desbordamiento. Al igual que en los lenguajes de programación C, C++, si la suma de dos números grandes supera los 10^18, se produce un desbordamiento y comenzamos a obtener resultados inesperados.
Demostración: Aquí probaremos para dos números y por lo tanto se puede generalizar para más de dos números.
Let a % m = r1
and b % m = r2
Then a and b can be written as (using quotient theorem).
Here q1 is quotient when we divide a by m and r1 is remainder.
Similar meanings are there for q2 and r2
a = m x q1 + r1
b = m x q2 + r2
LHS = (a + b) % m
= ((m x q1 + r1 ) + (m x q2 + r2) ) % m
= (m x (q1 + q2) + r1 + r2 ) % m
We can eliminate the multiples of m when we take the mod m.
Then,
LHS = (r1 + r2) % m
RHS = (a % m + b % m) % m
= (r1 + r2) % m
Hence, LHS = RHS