A continuación se presentan algunas propiedades interesantes de la multiplicación modular
(axb) mod m = ((a mod m) x (b mod m)) mod m
(axbxc) mod m = ((a mod m) x (b mod m) x (c mod m)) mod m
La misma propiedad se cumple para más de tres números.
La fórmula anterior es la versión extendida de la siguiente fórmula:
Ejemplo 1:
Encontrar el resto de 15 x 17 x 19 al dividir por 7.
Solución:
Al dividir 15 por 7 nos queda 1 como resto.
Al dividir 17 por 7 nos queda 3 como resto.
Al dividir 19 entre 7 nos queda 5 como resto.
El resto de la expresión (15 x 17 x 19)/7 será igual a (1 x 3 x 5)/7.
El resto combinado será igual al resto de 15/7, es decir, 1.
Ejemplo 2:
Hallar el resto de 1421 x 1423 x 1425 al dividirlo por 12.
Solución:
Al dividir 1421 entre 12 nos queda 5 de resto.
Al dividir 1423 por 12 nos queda 7 como resto.
Al dividir 1425 por 12 nos queda 9 como resto.
Rem [(1421 x 1423 x 1425)/12] = Rem [(5 x 7 x 9)/12]
Rem [(35 x 9)/12] = Rem [(11 x 9)/12]
Rem [99/ 12] = 3.
¿Cómo es útil?
Si necesitamos encontrar el resto de la multiplicación de dos números grandes, podemos evitar hacer la multiplicación de números grandes, especialmente útil en la programación donde la multiplicación de números grandes puede causar desbordamiento.
Demostración: Si demostramos para dos números, entonces podemos generalizarlo fácilmente. Veamos la demostración 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 x b) % m
= ((m x q1 + r1 ) x (m x q2 + r2) ) % m
= (m x m x q1 x q2 +
m x q1 x r2 +
m x q2 x r1 + r1 x r2 ) % m
= (m x (m x q1 x q2 + q1 x r2 +
q2 x r1) +
r1 x r2 ) % m
We can eliminate the multiples of m when
we take the mod m.
LHS = (r1 x r2) % m
RHS = (a % m x b % m) % m
= (r1 x r2) % m
Hence, LHS = RHS