26. Modulare Arithmetik
Fermats kleiner Satz
Niveau: fortgeschritten
Formel
Detail
Zentrales Ergebnis für modulare Arithmetik und Kryptographie.
Idee erkunden
Vas a ver cómo las potencias de a recorren residuos módulo p. Si p es primo y a no es múltiplo de p, Fermat garantiza que en el exponente p−1 el resultado es 1.
Pruébalo — Elige p y a, avanza potencia por potencia y observa dónde cae cada residuo.
p = 7 primo ✓a = 3 p ∤ a ✓gcd(3,7)=1 ✓
Conclusión esperada: 3^6 ≡ 1 (mod 7)
k
3^k
k0
Paso 0
a^0 ≡ 1 (mod 7)
Orden de 3 mod 7 = 6
a3
Módulo 7, base 3, exponente 0, residuo 1.
Paso 0/6 · 3^0 ≡ 1 (mod 7)