26. Modular arithmetic
Modular inverse
Level: intermediate
Formula
Detail
The inverse exists exactly when a and n are coprime.
Explore the idea
Vas a buscar el residuo que, al multiplicarse por a, produce 1 módulo m. Ese residuo es el inverso modular de a.
Pruébalo — Cambia el candidato y observa cuándo a·x mod m llega exactamente a 1.
a = 3m = 7gcd(3,7)=1inverso garantizado ✓
a·x ≡ 1 (mod 7)
Inverso encontrado
x = 5
3 × 5 = 15
15 = 2·7 + 1
15 mod 7 = 1
3⁻¹ ≡ 5 (mod 7)
m7
a3
x5
3 por 5 es 15. Residuo 1 módulo 7. 5 es el inverso.
a=3 · m=7 · candidato x=5 · 3×5 mod 7=1 · inverso ✓