Reglas para (a × b) mod n.
La multiplicación módulo $n$ es una operación fundamental en teoría de números que te permite analizar el residuo de un producto al dividirlo entre un módulo $n$. El principio central es que la operación de multiplicar es compatible con la relación de congruencia. Esto significa que para encontrar el residuo de un producto grande, como $1234 \times 5678 \pmod{10}$, no necesitas hacer toda la multiplicación primero. En lugar de eso, puedes reemplazar cada factor con su residuo módulo $n$, multiplicar esos números más pequeños y luego sacarle el residuo al resultado. Esta propiedad hace que la aritmética modular sea una herramienta súper potente para simplificar cálculos con números grandotes.
Este concepto aparece por todos lados en competencias de mate como el AMC 10 y AMC 12, sobre todo en problemas donde tienes que hallar las últimas cifras de un número (módulo 10 o 100) o determinar la divisibilidad. Más allá de los trucos para calcular, la multiplicación mod $n$ es la base de estructuras algebraicas llamadas anillos y campos. A diferencia de la multiplicación normal con números reales, la multiplicación módulo $n$ tiene propiedades únicas que dependen del módulo; por ejemplo, si $n$ es compuesto, el producto de dos enteros que no son cero puede dar cero módulo $n$ (divisores de cero), mientras que si $n$ es primo, la estructura se porta más como la aritmética estándar donde puedes dividir entre cualquier elemento que no sea cero.
Para que te des una idea, puedes visualizar la multiplicación mod $n$ como aritmética en un círculo o un reloj con $n$ posiciones marcadas del $0$ al $n-1$. Cuando multiplicas dos números, vas dando vueltas al círculo. La clave aquí es que la "posición" en el reloj depende solo de las posiciones iniciales de los factores, no de cuántas vueltas completas (múltiplos de $n$) representen. Esto te permite ignorar los múltiplos de $n$ en cualquier paso de tu cuenta sin que afecte la clase de congruencia final.
La propiedad fundamental de la multiplicación modular dice que si dos números son congruentes a sus residuos, su producto es congruente al producto de esos residuos.
La Propiedad de la Multiplicación: $$ (a \times b) \pmod n \equiv ((a \pmod n) \times (b \pmod n)) \pmod n $$
Relación de Congruencia: Si $a \equiv c \pmod n$ y $b \equiv d \pmod n$, entonces: $$ a \cdot b \equiv c \cdot d \pmod n $$
Exponenciación (Multiplicación Repetida): Como consecuencia directa, para cualquier entero positivo $k$: $$ a^k \equiv (a \pmod n)^k \pmod n $$
Inverso Modular: Aunque no es una fórmula directa para multiplicar, el concepto de división se define a través de la multiplicación. Un entero $a$ tiene un inverso multiplicativo $a^{-1}$ módulo $n$ si y solo si $\gcd(a, n) = 1$. Si existe, se cumple que: $$ a \cdot a^{-1} \equiv 1 \pmod n $$
Teorema: Sea $n$ un entero positivo. Si $a \equiv c \pmod n$ y $b \equiv d \pmod n$, entonces $ab \equiv cd \pmod n$.
Demostración:
Definición de Congruencia: Por la definición de congruencia modular, $x \equiv y \pmod n$ implica que $x - y$ es un múltiplo de $n$. Por lo tanto, puedes escribir $x$ en términos de $y$ y un múltiplo entero de $n$.
Como $a \equiv c \pmod n$, existe un entero $k$ tal que: $$ a = kn + c $$
Como $b \equiv d \pmod n$, existe un entero $j$ tal que: $$ b = jn + d $$
Multiplicación: Ahora, multiplica las expresiones de $a$ y $b$: $$ a \cdot b = (kn + c)(jn + d) $$
Expansión: Expande el producto usando la propiedad distributiva: $$ ab = (kn)(jn) + (kn)(d) + (c)(jn) + cd $$ $$ ab = kjn^2 + kdn + cjn + cd $$
Factorización: Puedes factorizar $n$ de los primeros tres términos: $$ ab = n(kjn + kd + cj) + cd $$
Conclusión: Pon que $M = kjn + kd + cj$. Como $k, j, c, d$ y $n$ son todos enteros, $M$ tiene que ser un entero. Así que: $$ ab = n \cdot M + cd $$
Si reacomodas esta ecuación, obtienes: $$ ab - cd = n \cdot M $$
Esto muestra que la diferencia $ab - cd$ es divisible entre $n$. Por la definición de congruencia, esto significa que: $$ ab \equiv cd \pmod n $$
$\square$