Olimpiada Oaxaqueña de Informática
Matemáticasmatemáticasmóduloaritmética-modularexponenciacióninverso

Aritmética Modular

Domina la aritmética modular: operaciones, exponenciación rápida e inverso modular

OOI Oaxaca9 de febrero de 20269 min read

¿Qué es la aritmética modular?

La aritmética modular trabaja con los residuos de la división. Cuando decimos amod  ma \mod m, nos referimos al residuo de dividir aa entre mm.

17mod  5=2porque17=3×5+217 \mod 5 = 2 \quad \text{porque} \quad 17 = 3 \times 5 + 2

En programación competitiva, frecuentemente trabajamos con módulos grandes como 109+710^9 + 7 para evitar overflow y mantener los números manejables.

Notación

Escribimos a≡b(modm)a \equiv b \pmod{m} para indicar que aa y bb tienen el mismo residuo al dividir por mm.

17≡2(mod5)17 \equiv 2 \pmod{5} 17≡12(mod5)17 \equiv 12 \pmod{5} 17≡−3(mod5)17 \equiv -3 \pmod{5}

Operaciones básicas

Propiedades fundamentales

Para cualesquiera aa y bb:

  1. (a+b)mod  m=((amod  m)+(bmod  m))mod  m(a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m
  2. (a−b)mod  m=((amod  m)−(bmod  m)+m)mod  m(a - b) \mod m = ((a \mod m) - (b \mod m) + m) \mod m
  3. (a×b)mod  m=((amod  m)×(bmod  m))mod  m(a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m

⚠️ Cuidado: La división NO funciona así. Necesitamos el inverso modular.

Implementación en C++

const int MOD = 1e9 + 7;

long long suma(long long a, long long b) {
    return ((a % MOD) + (b % MOD)) % MOD;
}

long long resta(long long a, long long b) {
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

long long multiplica(long long a, long long b) {
    return ((a % MOD) * (b % MOD)) % MOD;
}

Ejemplo: Suma grande

Calcular (1018+1018)mod  (109+7)(10^{18} + 10^{18}) \mod (10^9 + 7):

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    long long a = 1e18;
    long long b = 1e18;

    // Sin módulo: overflow!
    // cout << a + b << endl;  // ERROR

    // Con módulo: correcto
    long long resultado = ((a % MOD) + (b % MOD)) % MOD;
    cout << resultado << endl;  // Funciona correctamente

    return 0;
}

Exponenciación Modular

Calcular anmod  ma^n \mod m de manera eficiente.

Método ingenuo

long long potenciaIngenua(long long base, long long exp, long long mod) {
    long long resultado = 1;
    for (int i = 0; i < exp; i++) {
        resultado = (resultado * base) % mod;
    }
    return resultado;
}

Complejidad: O(n)O(n) - Muy lento para exponentes grandes como 101810^{18}.

Exponenciación binaria (rápida)

Usamos la propiedad:

(a^{n/2})^2 & \text{si } n \text{ es par} \\ a \cdot a^{n-1} & \text{si } n \text{ es impar} \end{cases}$$ ```cpp long long potencia(long long base, long long exp, long long mod) { long long resultado = 1; base %= mod; while (exp > 0) { // Si el bit actual es 1, multiplicamos if (exp & 1) { resultado = (resultado * base) % mod; } // Elevamos la base al cuadrado base = (base * base) % mod; // Dividimos el exponente entre 2 exp >>= 1; } return resultado; } ``` **Complejidad:** $O(\log n)$ - ¡Muy rápido! ### Ejemplo paso a paso Calcular $3^{13} \mod 7$: ``` 13 en binario = 1101 exp = 13 (1101): resultado = 1 * 3 = 3, base = 3² = 9 ≡ 2 exp = 6 (110): (bit 0), base = 2² = 4 exp = 3 (11): resultado = 3 * 4 = 12 ≡ 5, base = 4² = 16 ≡ 2 exp = 1 (1): resultado = 5 * 2 = 10 ≡ 3, base = 2² = 4 Resultado: 3 Verificación: 3^13 = 1594323, 1594323 mod 7 = 3 ✓ ``` ### Versión recursiva ```cpp long long potenciaRecursiva(long long base, long long exp, long long mod) { if (exp == 0) return 1; long long mitad = potenciaRecursiva(base, exp / 2, mod); mitad = (mitad * mitad) % mod; if (exp % 2 == 1) { mitad = (mitad * base) % mod; } return mitad; } ``` ## Inverso Modular El **inverso modular** de $a$ módulo $m$ es un número $x$ tal que: $$a \cdot x \equiv 1 \pmod{m}$$ Lo denotamos como $a^{-1} \mod m$. ### ¿Cuándo existe? El inverso modular de $a$ módulo $m$ existe **si y solo si** $\gcd(a, m) = 1$ (son coprimos). ### Método 1: Pequeño Teorema de Fermat Si $p$ es primo y $\gcd(a, p) = 1$: $$a^{p-1} \equiv 1 \pmod{p}$$ Por lo tanto: $$a^{-1} \equiv a^{p-2} \pmod{p}$$ ```cpp long long inverso(long long a, long long p) { return potencia(a, p - 2, p); } ``` **Complejidad:** $O(\log p)$ > 📝 **Nota:** Este método solo funciona si el módulo es primo. ### Método 2: Algoritmo de Euclides Extendido Funciona para cualquier módulo (siempre que $\gcd(a, m) = 1$): ```cpp long long gcdExtendido(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long x1, y1; long long g = gcdExtendido(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return g; } long long inverso(long long a, long long m) { long long x, y; long long g = gcdExtendido(a, m, x, y); if (g != 1) return -1; // No existe inverso return (x % m + m) % m; } ``` ### Método 3: Precálculo de inversos (1 a n) Útil cuando necesitas muchos inversos: ```cpp const int MOD = 1e9 + 7; const int MAXN = 1e6; long long inv[MAXN + 1]; void precalcularInversos() { inv[1] = 1; for (int i = 2; i <= MAXN; i++) { inv[i] = (MOD - (MOD / i) * inv[MOD % i] % MOD) % MOD; } } ``` **Complejidad:** $O(n)$ precálculo, $O(1)$ por consulta. ## División Modular Para calcular $\frac{a}{b} \mod m$, multiplicamos por el inverso: $$\frac{a}{b} \mod m = (a \cdot b^{-1}) \mod m$$ ```cpp long long division(long long a, long long b, long long mod) { return (a % mod) * potencia(b, mod - 2, mod) % mod; } ``` ### Ejemplo Calcular $\frac{10}{3} \mod 7$: 1. Encontrar $3^{-1} \mod 7$: $3^{-1} \equiv 3^5 \equiv 243 \equiv 5 \pmod{7}$ 2. Calcular $10 \times 5 \mod 7 = 50 \mod 7 = 1$ Verificación: Si el resultado es $x$, entonces $3x \equiv 10 \pmod{7}$. $3 \times 1 = 3$ y $10 \mod 7 = 3$. ✓ ## Template completo para aritmética modular ```cpp #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; long long suma(long long a, long long b) { return ((a % MOD) + (b % MOD)) % MOD; } long long resta(long long a, long long b) { return ((a % MOD) - (b % MOD) + MOD) % MOD; } long long mult(long long a, long long b) { return ((a % MOD) * (b % MOD)) % MOD; } long long potencia(long long base, long long exp) { long long resultado = 1; base %= MOD; while (exp > 0) { if (exp & 1) resultado = mult(resultado, base); base = mult(base, base); exp >>= 1; } return resultado; } long long inverso(long long a) { return potencia(a, MOD - 2); } long long division(long long a, long long b) { return mult(a, inverso(b)); } int main() { // Ejemplo: calcular (10! / 5!) mod (10^9 + 7) long long numerador = 1; for (int i = 1; i <= 10; i++) { numerador = mult(numerador, i); } long long denominador = 1; for (int i = 1; i <= 5; i++) { denominador = mult(denominador, i); } cout << division(numerador, denominador) << endl; // 30240 return 0; } ``` ## Problemas comunes ### Problema 1: Potencia grande Calcular $a^b \mod (10^9 + 7)$ donde $a, b \leq 10^{18}$: ```cpp #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; long long potencia(long long base, long long exp, long long mod) { long long resultado = 1; base %= mod; while (exp > 0) { if (exp & 1) resultado = resultado * base % mod; base = base * base % mod; exp >>= 1; } return resultado; } int main() { long long a, b; cin >> a >> b; cout << potencia(a, b, MOD) << endl; return 0; } ``` ### Problema 2: Suma de potencias Calcular $\sum_{i=1}^{n} i^k \mod (10^9 + 7)$: ```cpp #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; long long potencia(long long base, long long exp, long long mod) { long long resultado = 1; base %= mod; while (exp > 0) { if (exp & 1) resultado = resultado * base % mod; base = base * base % mod; exp >>= 1; } return resultado; } int main() { long long n, k; cin >> n >> k; long long suma = 0; for (long long i = 1; i <= n; i++) { suma = (suma + potencia(i, k, MOD)) % MOD; } cout << suma << endl; return 0; } ``` ### Problema 3: Multiplicación de matrices modular Útil para recurrencias lineales: ```cpp #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; typedef vector<vector<long long>> Matrix; Matrix multiplicar(Matrix& A, Matrix& B) { int n = A.size(); Matrix C(n, vector<long long>(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; } Matrix potenciaMatriz(Matrix A, long long exp) { int n = A.size(); Matrix resultado(n, vector<long long>(n, 0)); // Matriz identidad for (int i = 0; i < n; i++) { resultado[i][i] = 1; } while (exp > 0) { if (exp & 1) resultado = multiplicar(resultado, A); A = multiplicar(A, A); exp >>= 1; } return resultado; } // Calcular el n-ésimo Fibonacci en O(log n) long long fibonacci(long long n) { if (n <= 1) return n; Matrix base = {{1, 1}, {1, 0}}; Matrix resultado = potenciaMatriz(base, n - 1); return resultado[0][0]; } int main() { long long n; cin >> n; cout << fibonacci(n) << endl; return 0; } ``` ## Resumen | Operación | Fórmula | Complejidad | |-----------|---------|-------------| | Suma | $(a + b) \mod m$ | $O(1)$ | | Resta | $(a - b + m) \mod m$ | $O(1)$ | | Multiplicación | $(a \times b) \mod m$ | $O(1)$ | | Potencia | Exponenciación binaria | $O(\log n)$ | | Inverso | $a^{m-2} \mod m$ (Fermat) | $O(\log m)$ | | División | $a \times b^{-1} \mod m$ | $O(\log m)$ | ## Ejercicios recomendados 1. [Codeforces - Modular Exponentiation](https://codeforces.com/problemset/problem/913/A) 2. [CSES - Exponentiation](https://cses.fi/problemset/task/1095) 3. [CSES - Exponentiation II](https://cses.fi/problemset/task/1712) 4. [AtCoder - Div Game](https://atcoder.jp/contests/abc169/tasks/abc169_c)