Mod mit Logarithmus?
Hallo
Wie ist die Lösung gemeint?
Wie wird der Bezug gemacht?
2 Antworten
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik, Mathematik
Zu lösen ist die Gleichung 9^k = 16 (mod 17).
Man kann auf beiden Seiten den (diskreten) Logarithmus zur Basis 9 nehmen und erhält k = log(16) (mod 17). Eine eher ungewöhnliche Darstellung.
Zurück zur Gleichung, das kann man auch schreiben als 9^k = -1 (mod 17).
Quadrieren liefert 9^(2k) = 1 (mod 17).
Der kleine Fermatsche Satz sagt uns, dass 9^16 = 1 (mod 17).
Das heisst 2k teilt 16, oder k teilt 8. Man muss also nur k= 2, 4 und 8 probieren, bis es passt.
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik, Mathematik
9^4 = 6561 = 385 * 17 + 16
Wenn man die Lösung weiß, ist ihre Richtigkeit leicht zu zeigen.
Für beliebige Zahlen ist das allerdings recht schwer auszurechnen.