Si usted vino buscando un resumen, al final del post lo encontrará.

El residuo #

Seguramente cuando usted estaba en la primaria le enseñaron a dividir de una manera similar a la siguiente:

Donde se cumple que:

$$ \text{dividendo} = \text{divisor} \cdot \text{cociente} + \text{residuo} $$

Aunque cuando dividimos usualmente nos interesa el cociente, en este caso nos va a interesar el residuo.

En la mayoría de lenguajes de programación tenemos el operador $%$ para calcular el residuo de una división. Algunos ejemplos:

int r = 8 % 3; // r = 2
int r = 21 % 4; // r = 1
int r = 7 % 10; // r = 7
int r = 30 % 6; // r = 0

Algunas propiedades. Sea $r = k % m$:

• $0 \leq r < m$
• Si $0 \leq k < m$, entonces $r = k$
• Si $k$ es múltiplo de $m$, entonces $r = 0$

Cuidado con los números negativos #

Miremos este ejemplo para ver lo que pasa en los lenguajes de programación con números negativos y el operador $%$:

int m = 6;
int d = -16 / m; // d = -2
int r = -16 % m; // r = -4

Esto tiene sentido, ya que se cumple que -16 == 6 * (-2) + (-4).

Sin embargo, para hacer cálculos de aritmética modular preferimos que el residuo sea un número que cumpla con $0 \leq r < m$. Para conseguir este residuo no-negativo, hacemos $r = (k % m + m) % m$. En el ejemplo anterior nos quedaría:

int m = 6;
int r = (-16 % m + m) % m; // r = 2

Y la expresión quedaría -16 == 6 * (-3) + 2.

Congruencias #

Si dos números $x$ y $y$ tienen el mismo residuo con cierto $m$, decimos que $x$ y $y$ son congruentes módulo $m$, y lo denotamos de la siguiente manera:

$$ x \equiv y \pmod{m} $$

Algunos ejemplos:

• $7 \equiv 25 \pmod{3}$ ya que $7 % 3 = 1$ y $25 % 3 = 1$
• $20 \equiv 44 \pmod{8}$ ya que $20 % 8 = 4$ y $44 % 8 = 4$
• $52 \equiv 24 \pmod{7}$ ya que $52 % 7 = 3$ y $24 % 7 = 3$

Inverso modular #

El inverso modular de $x$ módulo $m$ es un número que denotamos como $x^{-1}$, y que al multiplicarlo por $x$, obtenemos que $x \cdot x^{-1} \equiv 1 \pmod{m}$

Algo que hay que anotar es que este inverso modular existe solamente si $x$ y $m$ son coprimos (es decir que no tienen factores en común).

Veamos algunos ejemplos:

• El inverso de $3$ módulo $26$ es $9$, ya que $9 \cdot 3 = 27$ y $27 % 26 = 1$
• El inverso de $11$ módulo $36$ es $23$, ya que $11 \cdot 23 = 253$ y $253 % 36 = 1$
• El inverso de $5$ módulo $8$ es $5$, ya que $5 \cdot 5 = 25$ y $25 % 8 = 1$
• El inverso de $6$ módulo $14$ no existe, ya que no son coprimos (tienen a $2$ como factor común)

Ahora la pregunta es, ¿cómo hallamos este inverso modular?

Pequeño teorema de Fermat #

No confundir con el Último Teorema de Fermat.

Este pequeño teorema establece que:

$$ \text{Si } m \text{ es primo, } a^{m-1} \equiv 1 \pmod{m} $$

Notemos que $a^{m-1} = a \cdot a^{m-2}$. Nos queda que:

$$ a \cdot a^{m-2} \equiv 1 \pmod{m} $$

Entonces por definición $a^{m-2}$ es el inverso modular de $a$.

Como dijimos anteriormente, el inverso modular sólo existe si $a$ y $m$ son coprimos. Como en este caso $m$ es primo, todos los $a$ tal que $0 < a < m$ son coprimos con $m$, y por lo tanto tienen inverso. Si $a > m$, sólo se cumplirá el teorema cuando sean coprimos.

Usamos la exponenciación logarítmica para encontrar $a^{m-2}$ rápidamente.

public static int MOD = 1000000007;

public static int expLogMod(int b, int e) {
    if(e == 0) return 1;

    int p = expLogMod(b, e/2);
    long q;

    if(e % 2 == 0) {
        q = (long)p * p;
    } else {
        q = ((long)p * p) % MOD * b;
    }
    return (int)(q % MOD);
}

public static int invMod(int a) {
    return expLogMod(a, MOD - 2);
}

Recomiendo leer el post hasta el final y luego regresar y corroborar este código.

Algoritmo de Euclides extendido #

Con este algoritmo podemos encontrar el inverso modular cuando $m$ no es primo. Para no alargar demasiado este post no lo voy a incluir aquí. El lector interesado puede ver una explicación e implementación en este link.

Propiedad distributiva #

El módulo tiene varias propiedades con la suma y la multiplicación, pero una que nos va a resultar especialmente útil es la distributiva:

• $(a_0 ​+ a_1 ​+ … + a_n​) % m = (a_0 ​% m + a_1 % m + … + a_n ​% m) % m$
• $(a_0 ​\cdot a_1 ​\cdot … \cdot a_n​) % m = (a_0 ​% m \cdot a_1 % m \cdot … \cdot a_n ​% m) % m$

En programación competitiva #

En algunos problemas de programación competitiva piden imprimir la respuesta “módulo $10^9 + 7$”. Esto sucede cuando la respuesta es un número muy grande. El máximo número que cabe en un int está alrededor de $10^9$, y en un long está alrededor de $10^{18}$. Imaginemos un problema que nos pide calcular $50!$. Esto no lo podremos hacer ni siquiera con long, ya que $50!$ está en el orden de $10^{64}$.

Por ende, los problemas no piden la solución exacta, sino la respuesta módulo $10^9 + 7$. Como $10^9 + 7$ cabe en un int, podemos almacenarla perfectamente. Además, $10^9 + 7$ es primo, por lo cual podemos usar el Pequeño Teorema de Fermat para calcular inversos modulares en caso de ser necesario.

Si intentamos calcular toda la respuesta del problema y tomar el módulo únicamente al final, vamos a tener overflow en los pasos intermedios y por tanto la respuesta incorrecta. La clave es usar la propiedad distributiva e ir tomando el módulo en cada paso. Veamos ejemplos:

La suma #

public static int MOD = 1000000007;

// MAL
public static int sum(int[] a) {
    int s = 0;
    for(int i=0; i<a.length; i++) {
        s = s + a[i]; // Puede dar overflow
    }
    return s % MOD;
}

// BIEN
public static int sum(int[] a) {
    int s = 0;
    for(int i=0; i<a.length; i++) {
        s = (s % MOD + a[i] % MOD) % MOD; // Módulo en cada paso
    }
    return s % MOD;
}

La resta #

Matemáticamente la propiedad distributiva de la suma se sigue cumpliendo para la resta ($(a - b) % m = (a % m - b % m) % m$). Sin embargo, a la hora de programar, el operador $%$ nos puede arrojar un número negativo como ya vimos anteriormente. Para obtener siempre un número positivo, hacemos:

$$ (a - b) % m = (a % m - b % m + m) % m $$

La multiplicación #

Con la multiplicación hay que tener cuidado: tanto $a % m$ como $b % m$ caben en un int, pero al hacer $(a % m \cdot b % m)$, es posible que haya overflow. Debemos utilizar un long para almacenar este producto. Luego, al sacarle el módulo, ya volvemos a obtener un valor que cabe en un int.

Por ejemplo, miremos esta función para calcular el factorial:

public static int MOD = 1000000007;

// MAL
public static int factorial(int n) {
    int f = 1;
    for(int i=2; i<=n; i++) {
        // Esto nos va a dar overflow y el resultado incorrecto
        f = f * i;
    }
    return f % MOD;
}

// BIEN
public static int factorial(int n) {
    // Debemos usar long para almacenar los pasos intermedios
    long f = 1;
    for(int i=2; i<=n; i++) {
        // Hacemos la multiplicación con módulo en cada paso
        f = (f * i) % MOD;
    }
    return (int)(f % MOD);
}

La división #

Incluir el inverso modular en el post no fue gratuito. Resulta que a diferencia de la suma, la multiplicación y la resta, la división no es tan sencilla:

$$ \left( \frac{a}{b} \right) % m \neq \left( \frac{a % m}{b % m} \right) % m $$

Para poder hacerlo, debemos encontrar el inverso modular de $b$ (módulo $m$), y usar la siguiente propiedad:

$$ \left( \frac{a}{b} \right) % m = ( a \cdot b^{-1} ) % m = ( a % m \cdot b^{-1} % m ) % m $$

Ya que $10^9 + 7$ es primo, podemos usar el Pequeño Teorema de Fermat para hallar el inverso modular de $b$. Si el problema pide otro módulo, hay que asegurarse de que sea primo, y en caso contrario, usar el Algoritmo de Euclides Extendido u otro algoritmo.

Resumen #

• $(a + b) % m = (a % m + b % m) % m$
• $(a - b) % m = (a % m - b % m + m) % m$
• $(a \cdot b) % m = (a % m \cdot b % m) % m$
• Para calcular $(\frac{a}{b}) % m$, debemos encontrar el inverso modular de $b$ (módulo $m$) y hacer $(a \cdot b^{-1}) % m = (a % m \cdot b^{-1} % m) % m$