La aritmética modular es la rama de la aritmética matemática relacionada con la funcionalidad “mod”. Básicamente, la aritmética modular está relacionada con el cálculo de «mod» de expresiones. Las expresiones pueden tener dígitos y símbolos computacionales de suma, resta, multiplicación, división o cualquier otro. Aquí discutiremos brevemente sobre todas las operaciones aritméticas modulares.
Teorema del Resto del Cociente:
Establece que, para cualquier par de enteros a y b (b es positivo), existen dos enteros únicos q y r tales que:
a = bxq + r
donde 0 <= r < b
Ejemplo:
Si a = 20, b = 6
entonces q = 3, r = 2
20 = 6 x 3 + 2
Suma modular:
la regla para la suma modular es:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
Ejemplo:
(15 + 17) % 7 = ((15 % 7) + (17 % 7)) % 7 = (1 + 3) % 7 = 4 % 7 = 4
La misma regla es para la resta modular. No requerimos mucha resta modular, pero también se puede hacer de la misma manera.
Multiplicación modular:
la regla para la multiplicación modular es:
(axb) mod m = ((a mod m) x (b mod m)) mod m
Ejemplo:
(12 x 13) % 5 = ((12 % 5) x (13 % 5)) % 5 = (2 x 3) % 5 = 6 % 5 = 1
División modular: la
división modular es totalmente diferente de la suma, resta y multiplicación modular. Tampoco existe siempre.
(a / b) mod m is not equal to ((a mod m) / (b mod m)) mod m.
Esto se calcula utilizando la siguiente fórmula:
(a / b) mod m = (ax (inverso de b si existe)) mod m
Inverso modular:
el inverso modular de un mod m existe solo si a y m son primos relativos, es decir, mcd (a, m) = 1.
Por lo tanto, para encontrar el inverso de a bajo módulo m,
si (axb) mod m = 1 entonces b es el inverso modular de a.
Ejemplo:
a = 5, m = 7
(5 x 3) % 7 = 1
por lo tanto, 3 es módulo inverso de 5 bajo 7.
Exponenciación modular:
Encontrar a^b mod m es la exponenciación modular. Hay dos enfoques para esto: recursivo e iterativo.
Ejemplo:
a = 5, b = 2, m = 7 (5 ^ 2) % 7 = 25 % 7 = 4
A continuación se presentan algunos conceptos más importantes relacionados con la aritmética modular