26. Modular arithmetic
Chinese remainder theorem
Level: advanced
Formula
Detail
Systems with pairwise coprime moduli have a unique solution modulo N.
Explore the idea
Vas a sincronizar dos relojes modulares: buscamos un mismo x que deje el residuo a módulo m₁ y el residuo b módulo m₂.
Pruébalo — Cambia los módulos y residuos y observa dónde coinciden ambas secuencias.
CONGRUENCIA 1
a=3
m7
x ≡ 3 (mod 7)
CONGRUENCIA 2
a=5
m5
x ≡ 0 (mod 5)
Normalizamos 5 módulo 5 → 0 (x ≡ 5 ≡ 0 (mod 5))
gcd(7,5)=1módulos coprimos ✓Periodo M = 35 = 7·5
módulo 7 · objetivo 3
x ≡ 3 (mod 7)
0 mod 7 = 0 ✗
0 mod 5 = 0 ✓
Todavía no coincide
módulo 5 · objetivo 0
x ≡ 0 (mod 5)
Primera congruencia x ≡ 3 mod 7. Segunda x ≡ 0 mod 5. Solución x ≡ 10 mod 35.
x ≡ 3 (mod 7) · x ≡ 0 (mod 5) · x=0 · (0,0) · solución x ≡ 10 (mod 35)