Calculadora de congruencias lineales — resuelve ax ≡ b (mod m)

Cómo funciona

ax ≡ b (mod m) tiene solución ⇔ g = mcd(a, m) divide a b · divide entre g: (a/g)x ≡ (b/g) (mod m/g) · x₀ = (b/g)·(a/g)⁻¹ mod (m/g) · todas las soluciones módulo m: x₀ + k·(m/g), k = 0, 1, …, g − 1

Una congruencia lineal es la versión modular de ax = b. Tiene solución exactamente cuando g = mcd(a, m) divide a b, y en ese caso tiene exactamente g soluciones módulo m. Al dividir a, b y m entre g queda una congruencia cuyo coeficiente es invertible, así que basta multiplicar por el inverso modular (hallado con el algoritmo de Euclides extendido) para obtener la solución única módulo m/g. Sumando múltiplos de m/g se obtienen todas las soluciones módulo m (Rosen, Elementary Number Theory, §4.2). Si a o b son negativos, primero se reducen módulo m.

Ejemplo resuelto

14x ≡ 30 (mod 100): mcd(14, 100) = 2, y 2 divide a 30, así que hay 2 soluciones. Dividiendo entre 2: 7x ≡ 15 (mod 50). El inverso de 7 módulo 50 es 43, porque 7 × 43 = 301 ≡ 1. Entonces x ≡ 15 × 43 = 645 ≡ 45 (mod 50). Módulo 100 las soluciones son 45 y 95. Comprobación: 14 × 45 = 630 ≡ 30 (mod 100).

Fuentes: Wolfram MathWorld — Linear Congruence Equation · Wikipedia — Linear congruence theorem

Preguntas frecuentes