Calculadora de Aritmética Modular

# Modular arithmetic operations

def mod_pow(base: int, exp: int, mod: int) -> int:
    """Fast modular exponentiation: base^exp mod m — O(log exp)."""
    return pow(base, exp, mod)  # Python built-in uses fast algorithm

def extended_gcd(a: int, b: int):
    """Extended Euclidean: returns (gcd, x, y) where a*x + b*y = gcd."""
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(a: int, m: int) -> int:
    """Modular inverse of a mod m (exists only if gcd(a,m) == 1)."""
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f"Inverse of {a} mod {m} does not exist")
    return x % m

def chinese_remainder(remainders, moduli):
    """Solve x ≡ r_i (mod m_i) using CRT (moduli must be pairwise coprime)."""
    N = 1
    for m in moduli:
        N *= m
    result = 0
    for r, m in zip(remainders, moduli):
        Ni = N // m
        result += r * Ni * mod_inverse(Ni, m)
    return result % N

# Examples
print(mod_pow(2, 10, 1000))          # 24  (2^10 = 1024 → 1024 mod 1000 = 24)
print(mod_inverse(3, 11))            # 4   (3 × 4 = 12 ≡ 1 mod 11)
print(chinese_remainder([2, 3, 2], [3, 5, 7]))  # 23 (x≡2 mod3, x≡3 mod5, x≡2 mod7)