---
tags: number-theory, modular-arithmetic, euclidean-division, modular-inverse, binary-exponentiation, fermat-little-theorem, divisibility, linear-congruences, chinese-remainder-theorem
---

# Aritmética modular

## Motivación
En muchos problemas, principalmente de combinatoria, la respuesta final puede ser un número muy muy grande, y en ellos pueden llegar a decirnos: "imprime la respuesta módulo $10^9+7$". Esto se hace con el fin de reducir la cantidad de dígitos a imprimir, simplificar los cálculos intermedios que nos toca hacer a nosotros, y evitar problemas de precisión/desbordamiento.

:::info
:information_source: **Ejemplo:** si el problema nos pide hallar $2^n$ para $n \leq 10^9$, vemos que los números crecen demasiado rápido, y el simplemente hecho de imprimirlos en consola puede llegar a ser tardado. Pero si modulamos la respuesta en $10^9+7$, siempre garantizaremos que el número no excederá $10^9+7$. Por ejemplo:
- $2^{100} = 1267650600228229401496703205376 \equiv 976371285 \mod {10^9+7}$.
:::

En estas notas veremos la teoría detrás de estos tipos de cálculos y algunas propiedades útiles.

## Definición
Sea $m$ un entero positivo, y sean $a,b \in \mathbb{Z}$. Diremos que $a$ es *congruente* a $b$ módulo $m$ si $a$ y $b$ dejan el mismo residuo al ser divididos entre $m$, es decir, $a \% m = b \% m$, y escribiremos:
$$
a \equiv b \mod{m}
$$

Sea $r$ el residuo en común que $a$ y $b$ dejan, entonces $a = q_1m + r$ y $b = q_2m + r$, lo que implica que $a-b = (q_1-q_2)m$, entonces se ve que $m \mid (a-b)$.

También se ve que si $m \mid a$, entonces $a \equiv 0 \mod{m}$.

:::info
:information_source: **Ejemplo:** Algunos ejemplos de congruencias son:
- $5 \equiv 19 \mod{7}$, pues $7$ divide a $19-5=14$.
- $-2 \equiv 18 \mod{10}$, pues $10$ divide a $18-(-2)=20$.
- $16 \equiv 0 \mod{4}$, pues $4$ divide a $16-0=16$.
- $16 \not \equiv 3 \mod{6}$, pues $6$ no divide a $16-3=13$.
:::

El objetivo principal de este tema en programación competitiva es encontrar $x \% m$, donde $x$ es un número muy grande y $m$ es un módulo de tamaño razonable. Es decir, aplicamos el algoritmo de la división a $x$ y a $m$: $x = mq + r$, y damos como respuesta a $r$. Dicho número también es de tamaño razonable, pues $0 \leq r < m$. Entonces, se ve por la definición que $x \equiv r \mod{m}$ y la $r$ es la mínima "representante" no negativa de $x$. Sin embargo, casi nunca podremos calcular $x$ de forma explícita y al final hallar el residuo con $m$, sino que tendremos que usar algunas propiedades.

La relación de congruencia $\equiv$ es:
- Reflexiva: $a \equiv a \mod{m}$
- Simétrica: si $a \equiv b \mod{m}$, entonces $b \equiv a \mod{m}$
- Transitiva: si $a \equiv b \mod{m}$ y $b \equiv c \mod{m}$, entonces $a \equiv c \mod{m}$

Por lo tanto, $\equiv$ es una relación de equivalencia, por lo que la podemos usar prácticamente de la misma manera en la que usamos la relación $=$.

:::info
:information_source: **Ejemplo:** trabajemos en módulo $m=5$. Tenemos las siguientes congruencias:
- $0 \equiv 5 \equiv 10 \equiv 15 \equiv \cdots \equiv -5 \equiv -10 \equiv -15 \equiv \cdots \mod{5}$
- $1 \equiv 6 \equiv 11 \equiv 16 \equiv \cdots \equiv -4 \equiv -9 \equiv -14 \equiv \cdots \mod{5}$
- $2 \equiv 7 \equiv 12 \equiv 17 \equiv \cdots \equiv -3 \equiv -8 \equiv -13 \equiv \cdots \mod{5}$
- $3 \equiv 8 \equiv 13 \equiv 18 \equiv \cdots \equiv -2 \equiv -7 \equiv -12 \equiv \cdots \mod{5}$
- $4 \equiv 9 \equiv 14 \equiv 19 \equiv \cdots \equiv -1 \equiv -6 \equiv -11 \equiv \cdots \mod{5}$

Entonces vemos que realmente solo hay $5$ elementos distintos (clases de equivalencia), y podemos usar todos los posibles residuos módulo $5$ para expresarlos: $\{0,1,2,3,4\}$. Otra forma de verlo, es que el $0$ es el "representante" del $0,5,10,15$; el $1$ representa a $1,6,11,16$; y así sucesivamente.
:::

Y de forma general, denotaremos como $\mathbb{Z}_m$ al conjunto de todas las clases de equivalencia módulo $m$. Usando los mínimos representantes, tenemos que $\mathbb{Z}_m = \{0, 1, 2, \ldots, m-1\}$.

## Propiedades

También tenemos las siguientes propiedades básicas de aritmética, similares a las de la igualdad simple:
- Si $a \equiv b \mod{m}$ y $c \equiv d \mod{m}$, entonces $a+c \equiv b+d \mod{m}$
- Si $a \equiv b \mod{m}$ y $c \equiv d \mod{m}$, entonces $ac \equiv bd \mod{m}$

Estas propiedades lo que nos dicen es que para calcular un número muy grande $x$ que por ahora solo conste de sumas, restas y multiplicaciones, realmente nunca tenemos que guardarlo completo, sino que en cada paso podemos ir "modulando". Veamos un ejemplo:

:::info
:information_source: **Ejemplo:** Sea $x=3 \times 2^4 + 7 - 18$ y queremos hallar $x \mod{5}$. De forma directa podemos calcular que $x=37$, por lo tanto $x \equiv 2 \mod{5}$, pero ahora hagámoslo por partes:
$$
\begin{align}
x &= 3 \times 2^4 + 7 - 18 \\
&\equiv 3 \times 2 \times 2 \times 2 \times 2 + 2 - 3 &\mod{5} \\
&\equiv 3 \times 4 \times 4 - 1 &\mod{5} \\
&\equiv 12 \times 4 - 1 &\mod{5} \\
&\equiv 2 \times 4 - 1 &\mod{5} \\
&\equiv 8 - 1 &\mod{5} \\
&\equiv 3 - 1 &\mod{5} \\
&\equiv 2 &\mod{5}
\end{align}
$$
:::

## Consideraciones en C++
### Arreglando las divisiones con números negativos
En C++ sabemos que tenemos los operadores de cociente ``/`` y residuo ``%``. Sin embargo, cuando queremos calcular $\lfloor a/b \rfloor$ o $a \% b$, donde $b$ es positivo pero $a$ puede ser cualquier entero, hay que tener cuidado. Veamos el siguiente código que intenta "comprobar" la validez del algoritmo de la división:

void division(int a, int b){
    int q = a/b, r = a%b;
    cout << a << " = (" << b << ")(" << q << ") + (" << r << ")\n";
}

division(14, 7);
division(-14, 7);

division(37, 7);
division(-37, 7);

Intentemos anticipar la salida del código anterior:
- Sabemos que el cociente entre $14$ y $7$ es $2$ y el residuo es $0$, por lo tanto la salida debería ser: ``14 = (7)(2) + (0)``
- Sabemos que el cociente entre $-14$ y $7$ es $-2$ y el residuo es $0$, por lo tanto la salida debería ser: ``-14 = (-7)(2) + (0)``
- Sabemos que el cociente entre $37$ y $7$ es $5$ y el residuo es $2$, por lo tanto la salida debería ser: ``37 = (7)(5) + (2)``
- Sabemos que el cociente entre $-37$ y $7$ es $-6$ y el residuo es $5$, por lo tanto la salida debería ser: ``-37 = (7)(-6) + (5)``

Vemos que la última salida no coincide y en realidad se imprimió ``-37 = 7(-5) + (-2)``. Aunque la igualdad es cierta, el residuo tiene signo negativo y el cociente es mayor en una unidad al que debería ser. Vemos que cuando $a$ es negativo y $b \mid a$, el signo del residuo también es negativo. Una forma de arreglarlo es la siguiente:

int Floor(int a, int b){
    int q = a/b;
    if(a < 0 && a%b != 0){
        q--;
    }
    return q;
}

int remainder(int a, int b){
    int r = a%b;
    if(a < 0 && r != 0){
        r += b;
    }
    return b;
}

### ¿Cómo sumar y multiplicar sin desbordar de forma eficiente?
El operador de módulo es costoso, por lo tanto hay que usarlo solo cuando sea necesario.

Supongamos que estamos trabajando en módulo $m$, y sean $a,b \in \mathbb{Z}$ tales que $0 \leq a,b < m$, es decir, ya están modulados. Supongamos que queremos hallar $(a+b) \mod {m}$, $(a-b) \mod{m}$ y $ab \mod{m}$ en código:
- **Suma:** Vemos que $0 \leq a+b \leq 2m-2$, por lo tanto una forma eficiente de calcularla es la siguiente:

int sum(int a, int b){
    int ans = a+b;
    if(ans >= m) ans -= m;
    return ans;
}

**Observación:** supongamos que el módulo $m$ cabe en un tipo de dato ``T``, entonces, dicho tipo de dato debe tener la capacidad para almacenar un valor de a lo más $2m-2$.

- **Resta:** Vemos que $-(m-1) \leq a-b \leq m-1$, entonces, una forma de calcularla:

int sub(int a, int b){
    int ans = a-b;
    if(ans < 0) ans += m;
    return ans;
}

**Observación:** supongamos que el módulo cabe en un tipo de dato ``T``, entonces ese tipo de dato debe tener la capacidad para almacenar valores en el rango $[-(m-1),m-1]$.

- **Multiplicación:** vemos que $0 \leq ab \leq (m-1)^2$. El límite superior ya creció mucho, por lo tanto un simple if no va a ajustar el valor, por lo que estaremos obligados a usar ``%``:

int mult(int a, int b){
    int ans = a*b % m;
    return ans;
}

**Observación:** si $m$ cabe en un tipo de dato ``T``, entonces ese tipo de dato debe tener la capacidad para almacenar valores de a lo más $(m-1)^2$, en otras palabras, el doble de capacidad. Es decir, si $m=10^9+7$, un ``int`` ya no va a ser suficiente para la respuesta intermedia antes de modular. Hay varias formas de hacerlo:
- La primera es llevar $a$ y $b$ en un ``long long``, hacer la multiplicación directa y modular.
- La otra es castear al menos uno de $a$ y $b$ a un tipo de dato más grande, hacer la multiplicación, modular y guardar la respuesta en un ``int``. El casteo se puede hacer al momento: ``(long long)a*b % m``, o ``1ll * a*b % m``.

## Inverso modular
La división es más interesante que las tres operaciones anteriores, ya que no necesariamente se cumple que: si $a \equiv b \mod{m}$ y $c \equiv d \mod{m}$, entonces $\frac{a}{c} \equiv \frac{b}{d} \mod{m}$.

:::info
:information_source: **Ejemplo:** sabemos que $\frac{60}{12}=5 \equiv 5 \mod{7}$, pero $\frac{60 \% 7}{12 \% 7}=\frac{4}{5}$ no se parece en nada a $5$.
:::

Sea $a \in \mathbb{Z}_m$. Definimos a $a^{-1} \in \mathbb{Z}_m$ como el *inverso multiplicativo modular* módulo $m$ si $a \cdot a^{-1} \equiv 1 \mod{m}$.

:::info
:information_source: **Ejemplo:** si $m=7$, tenemos los siguientes inversos:
- $0$ no tiene inverso.
- $1^{-1} \equiv 1 \mod{7}$
- $2^{-1} \equiv 4 \mod{7}$
- $3^{-1} \equiv 5 \mod{7}$
- $4^{-1} \equiv 2 \mod{7}$
- $5^{-1} \equiv 3 \mod{7}$
- $6^{-1} \equiv 6 \mod{7}$

Y del ejemplo anterior vemos que si reeemplazamos la división entre $5$ por una multiplicación con su inverso, obtenemos la respuesta correcta: $\frac{60}{12} \equiv \frac{4}{5} \equiv 4 \cdot 5^{-1} \equiv 4 \cdot 3 \equiv 12 \equiv 5 \mod{7}$.
:::

Por lo tanto, lo único que hay que hacer para calcular una fracción es reemplazar el denominador por el inverso multiplicativo modular, así estaremos reemplazando la división por multiplicación.

Para calcular $a^{-1}$ vemos que existen solo $m-1$ candidatos a ser su inverso, entonces podemos usar fuerza bruta para calcularlo, es decir, nos quedamos con el elemento $x$ que al multiplicarlo con $a$ nos de un residuo de $1$ módulo $m$. Pero la complejidad sería $O(m)$. Veamos otra forma:

Recordemos que el algoritmo extendido de Euclides nos devuelve para la entrada $(a,m)$ enteros $(x,y)$ tales que $ax+my=\gcd(a,m)$. Entonces:
$$
\begin{align}
ax + my &= \gcd(a,m) \\
ax &\equiv \gcd(a,m) \mod m
\end{align}
$$

Vemos que si imponemos la condición $\gcd(a,m)=1$, entonces $ax \equiv 1 \mod{m}$, por lo tanto, $x \equiv a^{-1} \mod m$.

De aquí vimos que el inverso de $a$ existe si y solo si $\gcd(a,m)=1$. La implementación queda como:

int inverse(int a, int m){
    auto[d, x, y] = extgcd(a, m); // en C++17 y posteriores
    // int d, x, y; tie(d, x, y) = extgcd(a, m); // en C++11 y anteriores
    if(d != 1){
        // el inverso no existe, hacer lo que sea necesario
        return -1;
    }
    if(x < 0) x += m; // x puede ser negativa
    return x;
}

Y la complejidad sigue siendo $O(\log m)$.

Si $m$ es un número primo, ¿qué puedo decir sobre la existencia de sus inversos? Se cumple que para todos los números $a$ en el rango $a \in [1,m-1]$ siempre va a existir su inverso, pues $\gcd(a,m)=1$. El único que no tendrá inverso es el $0$. Es por eso que usualmente nos dan módulos primos en los problemas, para no preocuparnos por esto.

Si $m$ no es primo y necesitamos calcular un inverso que no existe, tendremos que usar otras técnicas.

## Exponenciación y multiplicación binaria
Sea $a \in \mathbb{Z}$ y $n \in \mathbb{N}$. Queremos calcular $a^n$ de forma eficiente. Una forma es realizar las $n$ multiplicaciones con un ciclo ``for`` logrando una complejidad de $O(n)$. Introduciremos una forma que funciona en $O(\log n)$ y se basa en la exponenciación elevando al cuadrado sucesivamente.

Por ejemplo, si $n=20$, podemos hacer lo siguiente:
- $a^{20} = (a^{10})^2 = ((a^5)^2)^2 = ((a \cdot a^4)^2)^2 = ((a \cdot (a^2)^2)^2)^2 = ((a \cdot ((a)^2)^2)^2)^2$

Vemos que redujimos considerablemente el número de operaciones para hallar $a^{20}$. La idea fue que si el exponente es par, puedo ahorrarme la mitad de multiplicaciones al dividirlo entre 2, y si es impar puedo restarle 1 al exponente y ya se hace par. Es decir:

$$
a^n = \begin{cases}
(a^{n/2})^2 &\mbox{si $n$ es par} \\
a \cdot (a^{(n-1)/2})^2 &\mbox{si $n$ es impar}
\end{cases}
$$

Donde el caso base es cuando $n=0$, ahí tenemos que $a^0=1$.

Y la implementación queda como:

int power(int a, int n){
    if(n == 0){
        return 1;
    }else if(n%2 == 0){
        int tmp = power(a, n/2);
        return tmp*tmp;
    }else{
        int tmp = power(a, (n-1)/2);
        return a*tmp*tmp;
    }
}

Ahora analicemos la versión iterativa de este método. Supongamos de nuevo que quiero calcular $a^{20}$. Expresemos $20=10100_2$ y calculemos todas las potencias de $a$ cuyo exponente sea potencia de 2. Finalmente, multipliquemos solo las que me suman el exponente, es decir, las posiciones en 1 de la expansión en binario.

Ejemplo: primero tenemos que calcular $a^1$, $a^2$, $a^4$, $a^8$, $a^{16}$, $\ldots$. Calcularlas es fácil, pues un elemento de la lista se obtiene al elevar al cuadrado el anterior. Finalmente, nos fijamos en los bits prendidos de $n$ y multiplicamos las potencias de $a$ correspondientes. En el caso de $n=20$ solo tenemos prendidos los bits de $2^2$ y $2^4$, por lo tanto $a^{20} = a^4 \cdot a^{16}$.

Para implementarlo, podemos ir calculando las potencias de $a$ cuyos exponentes son potencias de 2 al vuelo mientras recorremos los bits de $n$ de derecha a izquierda. Cada que el bit menos significativo de $n$ esté prendido, multiplico a la respuesta la potencia actual de $a$.

int power(int a, int n){
    int ans = 1; // aquí llevaremos la respuesta, la inicializamos con 1 porque es el neutro de la multiplicación
    while(n){ // checamos los bits de n de derecha a izquierda
        if(n & 1) ans = ans * a; // cada que esté prendido el bit, multiplicamos la potencia actual de a
        n >>= 1; // corremos los bits de n a la derecha
        a = a * a; // calculamos in-place las potencias de a
    }
    return ans;
}

Podemos adaptar la exponenciación binaria para que calcule $a^n \mod {m}$. En cada multiplicación hay que hacer ``%m``, teniendo cuidado con no desbordar nada.

**Observación:** supongamos que $m=10^{18}+3$ y queremos hallar $a \cdot b \mod{m}$, donde $0 \leq a,b < m$. Si solo tenemos disponible un entero de a lo más 64 bits, ¿cómo la calculamos?

Tenemos que $0 \leq ab \leq (m-1)^2 \approx 10^{36}$, lo cual no cabe en un entero de 64 bits. Una forma de hacerlo es adaptar el método de la exponenciación binaria para que ahora sea multiplicación binaria.

Vemos que para la exponenciación usamos multiplicaciones, entonces ahora para la multiplicación usaremos sumas, es decir:
$$
a \cdot b = \begin{cases}
\left(a \cdot \frac{b}{2} \right) \cdot 2 &\mbox{si $b$ es par} \\
a + \left(a \cdot \frac{b-1}{2}\right) \cdot 2 &\mbox{si $b$ es impar}
\end{cases}
$$

Donde el caso base es que si $b=0$, entonces $a \cdot 0 = 0$. De esta forma, al solo multiplicar por 2 y sumar, las operaciones intermedias no crecen tanto y siguen cabiendo en un entero de 64 bits.

Esto se puede combinar para hallar $a^n \mod {m}$ bajo el mismo módulo grandote, cambiando las multiplicaciones de la exponenciación binaria por multiplicaciones binarias, logrando una complejidad de $O(\log^2 n)$.

### Módulos constantes
Si el módulo no cambia durante toda la ejecución del programa, podemos declararlo como variable global afuera del main como un valor **constante**. Por ejemplo, ``const int mod = 1e9 + 7``. Esto provocará que el compilador optimice todas las operaciones que involucren a ese módulo, reemplazando divisiones por multiplicaciones.

### Pequeño teorema de Fermat
Este teorema nos proporciona una forma alternativa de encontrar $a^{-1} \mod p$ para $1 \leq a < p$ y $p$ primo.

Sea $f(x) \equiv ax \mod{p}$. Por ejemplo, si $p=7$ y $a=2$, tenemos que:
- $f(1) = 2$
- $f(2) = 4$
- $f(3) = 6$
- $f(4) = 1$
- $f(5) = 3$
- $f(6) = 5$

Vemos que en la imagen de $f(x)$ todos los valores de $1$ a $p-1$ aparecen pero en otro orden. Por lo tanto, $f(x)$ es biyectiva, una correspondencia uno a uno. Entonces, tenemos que por la definición de $f(x)$:
$$
\begin{align}
\prod_{x=1}^{p-1} f(x) &\equiv \prod_{x=1}^{p-1} ax \equiv a^{p-1} \prod_{x=1}^{p-1} x \equiv a^{p-1} (p-1)! \mod{p}
\end{align}
$$

Pero por otro lado, como $f(x)$ permuta todos los valores de $1$ a $p-1$, entonces $\displaystyle \prod_{x=1}^{p-1} f(x) \equiv (p-1)! \mod{p}$. Igualando ambas expresiones, tenemos que:

$$
\begin{align}
a^{p-1} (p-1)! \equiv (p-1)! \mod{p} \\
a^{p-1} \equiv 1 \mod{p} \\
a^{p-2} \equiv a^{-1} \mod{p}
\end{align}
$$

Obtuvimos una forma de obtener $a^{-1}$ al calcular $a^{p-2} \mod{p}$. Esto se puede hacer con exponenciación binaria módulo $p$ con complejidad de $O(\log p)$.

Ejemplo: $2^{-1} \equiv 2^5 = 32 \equiv 4 \mod{7}$.

## Aplicaciones a criterios de divisibilidad
Sea $n$ expresado en base 10 dígito por dígito, es decir, $n=d_0 + d_1 \times 10 + d_2 \times 10^2 + \cdots$. Queremos saber si $n$ es divisible entre $m$ de forma eficiente cuando $n$ tiene muchos dígitos.

Tomemos $n$ junto con sus potencias de $10$ módulo $m$:
$$
n \equiv d_0 + d_1 \times 10 + d_2 \times 10^2 + \cdots \mod{m}
$$

Algunos ejemplos clásicos son:
- Si $m=2$, vemos que todas las potencias de $10$ son cero, por lo tanto $n \equiv d_0 \mod{2}$.
- Si $m=4$, todas las potencias a partir de $10^2$ son cero, por lo tanto $n \equiv d_0 + d_1 \times 10 \mod{4}$.
- Si $m=3$ tenemos que $10^k \equiv 1^k \equiv 1 \mod{3}$. Esto quiere decir que $n \equiv d_0 + d_1 + d_2 + \cdots \mod{3}$, es decir, para saber si $n$ es divisible entre $3$ solo me fijo si su suma de dígitos es divisible entre $3$.
- Si $m=5$ vemos que todas las potencias de $10$ son cero, por lo tanto, $n \equiv d_0 \mod{5}$.
- Si $m=6$, basta con ver si es divisible entre $2$ y entre $3$.
- Si $m=11$, tenemos que $10^k \equiv (-1)^k \mod{11}$, por lo tanto $n \equiv d_0 - d_1 + d_2 - d_3 + \cdots$, es decir, basta con ver si la suma alternada de dígitos es divisible entre 11.

De forma general, para cualquier $m$ puedo ir calculando las potencias sucesivas de $10$ moduladas e ir actualizando el número $n$.

Podemos ver también que si $\gcd(m,10)=1$, entonces las potencias de $10$ en algún punto se van a ciclar, es decir, $10^k \equiv 1 \mod{m}$, donde la mínima $k$ positiva que cumple es el tamaño del ciclo.

## Congruencias lineales
Sea $ax \equiv b \mod{m}$ una ecuación de primer grado módulo $m$, es decir, dados $a,b,m$, queremos hallar todas las $x$ que satisfagan la ecuación.

Ejemplo: si $4x \equiv 3 \mod{7}$, entonces $x \equiv 6 \mod{7}$, pues $4(6) = 24 \equiv 3 \mod{7}$.

Para resolverla, podemos usar casi las mismas reglas del álgebra normal, es decir, podemos sumar y restar a ambos lados lo que deseemos. Para la división hay que tener más cuidado, ya que el inverso puede o no existir.

Ejemplo: resolvamos $6x \equiv 4 \mod{8}$. Vemos que $x=2,6,10,\ldots$ son soluciones, es decir, $x \equiv 2 \mod{4}$. A pesar de que $6^{-1}$ no existe módulo $8$, la ecuación sí tiene soluciones.

De forma general, reescribamos $ax \equiv b \mod{m}$ como que $m \mid (b-ax)$, es decir, $b-ax=my$ para $y \in \mathbb{Z}$. Por lo tanto, $ax+my=b$.

Sea $d=\gcd(a,m)$, entonces al ejecutar el extgcd con entrada $(a,m)$ me va a devolver $(x_0,y_0)$ tal que $ax_0 + my_0 = d$. También sabemos que si $d \mid b$, podemos parametrizar a la familia de soluciones de $ax+my=b$ para $x$ como $x=x_0 \cdot \frac{b}{d} + \frac{m}{d} \cdot k$, o sea, $x \equiv x_0 \cdot \frac{b}{d} \mod{\frac{m}{d}}$.

Si regresamos al ejemplo de $6x \equiv 4 \mod{8}$, tenemos que $6x+8y=4$. Sabemos que $d=\gcd(6,8)=2$ y $2 \mid 4$, por lo tanto sí hay soluciones y están dadas por $x \equiv (-1) \cdot \frac{4}{2} \mod \frac{8}{2}$, o sea, $x \equiv 2 \mod 4$.

En conclusión, si queremos resolver $ax \equiv b \mod m$:
- Si $\gcd(a,m)=1$ simplemente multiplico ambos lados por $a^{-1}$.
- Si $\gcd(a,m) \neq 1$, entonces se tiene que cumplir que $\gcd(a,m) \mid b$. Si sí se cumple, puedo resolver la congruencia equivalente $a'x \equiv b' \mod m'$, donde $a'=\frac{a}{d}$, $b'=\frac{b}{d}$ y $m'=\frac{m}{d}$. Aquí el inverso de $a'$ módulo $m'$ ya existe, pues $\gcd(a', m')=\gcd(a/d, m/d) = 1$.

De hecho esto nos permite establecer la siguiente propiedad de cancelación: si $ad \equiv bd \mod{m}$, entonces $a \equiv b \mod{\frac{m}{\gcd(m,d)}}$.

## Teorema chino del residuo
Comencemos esta sección con un problema: tenemos un cofre del tesoro con cierto número de joyas. Si repartimos todas las joyas en partes iguales a 4 personas, sobran 3. Si las repartimos a 6 personas, sobran 5. Y si las repartimos a 5 personas, sobran 2. Hallar el mínimo número de joyas que el cofre tiene.

En otras palabras, sea $n$ el número de joyas. Podemos resumir lo que nos dice el problema como:
$$
\begin{align}
n &\equiv 3 \mod{4} \\
n &\equiv 5 \mod{6} \\
n &\equiv 2 \mod{5}
\end{align}
$$
Y queremos encontrar la mínima $n$ positiva que satisfaga simultáneamente las congruencias anteriores. Vemos que $\text{lcm}(4,6,5)=60$, eso quiere decir que si $n_0$ es una solución al sistema de congruencias, entonces también lo será $n_0+60$, $n_0+120$, etc, es decir, $n \equiv n_0 \mod 60$. Para hallar $n_0$ vemos que podemos iterar sobre todos los valores en el rango $[0,59]$ y ver quién satisface las tres congruencias al mismo tiempo. Luego de haber buscado el valor, tenemos $n \equiv 47 \mod 60$.

Intentemos optimizar la fuerza bruta con la siguiente observación. De la primera congruencia sabemos que $n=3,7,11,\ldots$. Por lo tanto, para la segunda congruencia solo checo dichos valores, es decir, doy saltos de $4$ en $4$ comenzando en $3$. Veo que $n_0=11$ satisface las dos primeras congruencias, por lo tanto, $n \equiv 11 \mod \text{lcm}(4,6)$, o sea, $n \equiv 11 \mod 12$. Por lo tanto, $n=11,23,35,47,\ldots$, por lo que para la tercer congruencia solo daré saltos de $12$ en $12$ comenzando en $11$ encontrando que $n \equiv 47 \mod \text{lcm}(12,5)$, o sea, $n \equiv 47 \mod 60$. La idea está basada en que podemos ir procesando congruencia por congruencia e irlas reduciendo hasta que solo me quede una.

De forma general, si tenemos $k$ congruencias con módulos $m_1, m_2, \ldots, m_k$, la complejidad de la idea anterior de ir aumentando el tamaño de salto en cada paso es de $O(m_1 + m_2 + \ldots m_k)$.

Para hallar la solución optimizada tenemos que hallar de forma óptima el salto que voy a ir dando y no con fuerza bruta:
- De la primer congruencia tenemos que $n=3+4t_1$ para $t_1 \in \mathbb{Z}$. Vemos que $t_1$ es el número de saltos que tengo que dar, para hallarlo podemos sustituir el valor de $n$ hasta ahora en la segunda congruencia: $3 + 4t_1 \equiv 5 \mod 6$, o sea, $4t_1 \equiv 2 \mod 6$. Esto es una congruencia lineal con $a=4$, $b=2$ y $m=6$. Vemos que $\gcd(a,m)=2$ y $2 \mid b$, por lo tanto sí hay soluciones y tengo ahora que resolver $2t_1 \equiv 1 \mod 3$. Multiplico ambos lados por $2^{-1}=2$ y queda $t_1 \equiv 2 \mod 3$, o sea, $t_1 = 2 + 3t_2$ para $t_2 \in \mathbb{Z}$. Sustituimos en $n$ y tenemos que $n=3+4(2+3t_2)=11+12t_2$, o sea, $n \equiv 11 \mod 12$.
- Procesemos la tercer congruencia. Sabemos que $n=11+12t_2$, entonces al sustituirlo en la tercer congruencia tenemos que $11+12t_2 \equiv 2 \mod 5$. Despejemos $t_2$ y queda: $12t_2 \equiv 2-11 \mod 5$, o sea $2t_2 \equiv 1 \mod 5$. Multipliquemos ambos lados por $2^{-1} = 3$ y tenemos $t_2 \equiv 3 \mod 5$. Por lo tanto, $t_2 = 3 + 5t_3$ para $t_3 \in \mathbb{Z}$. Sustituimos en $n$ y queda $n=11+12(3+5t_3)=47+60t_3$, es decir, $n \equiv 47 \mod 60$.

En el caso general supongamos que tenemos $k$ congruencias de la forma:
$$
\begin{cases}
n \equiv a_1 \mod m_1 \\
n \equiv a_2 \mod m_2 \\
\cdots \\
n \equiv a_k \mod m_k
\end{cases}
$$

Donde $0 \leq a_i < m_i$ y $m_i \geq 1$. Procesemos una por una y vayamos actualizando la solución global, es decir, $n \equiv r \mod M$.

La solución global al principio es $r \gets a_1$ y $M \gets m_1$, es decir, $n = r + Mt_1$.
- Supongamos que estamos procesando la $i$-ésima congruencia ($i \geq 2$), o sea, $n \equiv a_i \mod m_i$. Sustituimos y queda $r + Mt_1 \equiv a_i \mod m_i$, es decir, $Mt_1 \equiv a_i - r \mod m_i$. Sea $d=\gcd(M, m_i)$, entonces hay solución si y solo si $d \mid a_i-r$. Si sí hay, entonces $\frac{M}{d} t_1 \equiv \frac{a_i-r}{d} \mod \frac{m_i}{d}$. El valor de $\left( \frac{M}{d} \right)^{-1} \mod \frac{m_i}{d}$ ya existe, por lo tanto $t_1 \equiv \left( \frac{M}{d} \right)^{-1} \left( \frac{a_i-r}{d} \right) \equiv r_1 \mod \frac{m_i}{d}$. Por lo tanto, $t_1 = r_1 + \frac{m_i}{d}t_2$. Sustituyo y tengo que $n=r + M \left( r_1 + \frac{m_i}{d}t_2 \right) = r + Mr_1 + \frac{M m_i}{d}t_2$, o sea, $n \equiv r + M r_1 \mod \text{lcm}(M, m_i)$. Actualizamos nuestra solución global, es decir, $r \gets r + Mr_1$ y $M \gets \text{lcm}(M, m_i)$.
- Repetimos el paso anterior con las congruencias restantes hasta que hayamos procesado todas.

La implementación queda como:

pair<int, int> crt(const vector<int>& a, const vector<int>& m){
    int r = a[0], M = m[0];
    for(int i = 1; i < a.size(); i++){
        int d = __gcd(M, m[i]);
        if((a[i] - r) % d != 0){
            return {-1, -1}; // no hay solucion
        }
        int mod = m[i] / d;
        int r1 = (long long)inverse(M/d, mod) * ((a[i] - r) / d % mod) % mod;
        if(r1 < 0) r1 += mod;
        r += M*r1;
        M *= mod;
    }
    return {r, M};
}

Algunas observaciones:
- La complejidad de esta idea es $O(\log m_1 + \log m_2 + \cdots + \log m_k)$.
- El tipo de dato en el que guardemos $r$ y $M$ debe tener la capacidad para guardar números de a lo más $\text{lcm}(m_1, m_2, \ldots, m_k)$.
- Al hacer la actualización siempre tendremos que $r + Mr_1 < \text{lcm}(M,m_i)$, ya que:
$$
r + Mr_1 \leq M-1 + M \left( \frac{m_i}{d}-1 \right) = M-1 + \text{lcm}(M,m_i) - M = \text{lcm}(M,m_i) - 1 < \text{lcm}(M,m_i)
$$
Por lo tanto nunca tendremos que preocuparnos por modular la respuesta global con el módulo global. Esto es bueno, pues si suponemos que módulo global puede ir hasta $10^{18}$ y solo tenemos enteros de 64 bits, no tendremos que recurrir a la multiplicación binaria o cosas así.
- Los únicos módulos por los que hay que preocuparnos son los individuales. En muchos problemas se cumple que $m_i \leq 10^9$ y $\text{lcm}(m_1, m_2, \ldots, m_k) \leq 10^{18}$, por lo tanto usar puros ``long long`` en lugar de ``int`` en la implementación es suficiente.

**Ejercicio para el lector:** modificar la implementación para que en lugar de hacer dos llamadas a ``__gcd`` y a ``inverse``, solo se haga una a ``extgcd``. Demostrar la equivalencia.