Exploremos la propiedad multiplicativa de la aritmética modular:

(A * B) mod C = (A mod C * B mod C) mod C

Ejemplo de multiplicación:

Sean A=4, B=7, C=6.
Verifiquemos: (A * B) módulo C = (A módulo C * B módulo C) módulo C
LI= lado izquierdo de la ecuación.
LD= lado derecho de la ecuación.
LI = (A * B) mod C
LI = (4 * 7) mod 6
LI = 28 mod 6
LI = 4
LD = (A mod C * B mod C) mod C
LD = (4 mod 6 * 7 mod 6) mod 6
LD = (4 * 1) mod 6
LD = 4 mod 6
LD = 4
LI = LD = 4

Prueba de la multiplicación modular

Probaremos que (A * B) mod C = (A mod C * B mod C) mod C
Debemos mostrar que LI = LD
A partir del teorema del cociente y del residuo podemos escribir A y B como:
A = C * C1 + R1 donde 0 ≤ R1 < C y C1 es un integral. A módulo C = R1
B = C * C2 + R2 donde 0 ≤ R2 < C y C2 es un integral. B módulo C = R2
LI = (A * B) mod C
LI = ((C * C1 + R1 ) * (C * C2 + R2) ) mod C
LI = (C * C * C1 * C2 + C * C1 * R2 + C * C2 * R1 + R1 * R2 )  mod C
LI = (C * (C * C1 * C2 + C1 * R2 + C2 * R1)  + R1 * R2 )  mod C
Podemos eliminar los múltiplos de C cuando tomamos el módulo C:
LI = (R1 * R2) mod C
Ahora hagamos el LD
LD = (A mod C * B mod C) mod C
LI = (R1 * R2 ) mod C
Por lo tanto, LD = LI
LI = LD = (R1 * R2 ) mod C