El método para encontrar soluciones enteras x a congruencias de la forma a x ≡ b (mod n), donde a, b y n son enteros dados y n>0.

Principio

La congruencia a x ≡ b (mod n) es soluble exactamente cuando d = mcd(a,n) divide a b; si es soluble se divide por d para obtener una congruencia equivalente con módulo n/d y se usan inversos modulares sobre el coeficiente reducido.

Demostración

Ejemplo: resolver 14 x ≡ 6 (mod 20). mcd(14,20)=2 divide 6, dividir por 2: 7 x ≡ 3 (mod 10). El inverso de 7 módulo 10 es 3, luego x ≡ 3·3 ≡ 9 (mod 10). Al volver al módulo 20 las clases soluciones son x ≡ 9 y x ≡ 19 (mod 20).

Aplicación incorrecta

Intentar invertir a modulo n cuando mcd(a,n) ≠ 1 o ignorar el factor d provoca afirmaciones erróneas sobre unicidad o pérdida de soluciones.

Consecuencia

La aplicación correcta produce todas las clases residuo de soluciones enteras y una congruencia reducida cuya solución se parametriza mediante el módulo n/d; transforma una prueba de existencia en una construcción explícita útil en teoría de números computacional.

Inversión

En lugar de resolver x en una congruencia lineal única, puede invertirse el problema (caracterizar a o n a partir de clases observadas) o reemplazarse por la resolución de congruencias no lineales, que requieren criterios distintos.

Límite

Se aplica únicamente a congruencias lineales con coeficientes enteros y módulo n>0; excluye congruencias no lineales, congruencias sobre anillos no enteros y soluciones en Q salvo que se reduzcan a congruencias enteras equivalentes.

Tensión semántica

A menudo se confunde con resolver ecuaciones lineales sobre el anillo Z/nZ como objeto algebraico; la tensión radica entre la solución constructiva y explícita (clases residuo) y las declaraciones estructurales sobre módulos sobre Z/nZ.

Síntesis

Resolver congruencias lineales es el proceso constructivo que verifica la divisibilidad por mcd(a,n), reduce el módulo y produce inversos modulares cuando existen o una parametrización completa de las clases residuo que satisfacen a x ≡ b (mod n).