Hallo zusammen,
Aufgabe ist die Zahl 10^(10^100) modulo 71 zu rechnen und zwar mithilfe des Satzes von Euler-Fermat und dem Square-and-multiply Algorythmus.
Ich bin soweit gekommen:
10^(10^100) = 10^(10^70 * 10^30)
da phi(71) = 70 ==> 10^(1 * 10^30)
und hier komme ich nicht mehr weiter bzw ob das überhaupt richtig ist?
wäre super wenn jemand helfen könnte.
mfg Sque
Hallo Sque,
das ist gar nicht so wild. Bestimme m := 10100 mod 70. Der Sinn dahinter ist die Kongruenz 1010^100 ≡ 10m (mod 71). Beweise das selbst mit Euler-Fermat. Übrig bleibt damit die Berechnung von 10m mod 71 und die kannst Du dank genügend kleinem m mit der Square-And-Multiply-Methode bewältigen. Auch m bestimmst Du so.
http://de.wikipedia.org/wiki/Satz_von_Euler-Fermat
(Falls Du Deine Ergebnisse kontrollieren möchtest: Der Windows-Calculator im wissenschaftlichen Modus hat eine mod-Taste, und die funktioniert erstaunlicherweise noch bei hundertstelligen Zahlen.)
Gruß
Martin
Hallo Martin,
vielen dank, auf die richtige Lösung komme ich mit deinem Ansatz,
aber den Beweis dass 10^(10^100) ≡ 10^ (mod 71) bekomme ich nicht zustande.
Wäre super wenn du nochmal kurz helfen könntest.
vielen dank.
liebe grüße
Bonjour Sque,
zunächst ist 71 prim ⇒ φ(71) = 70 und damit ist nach dem Satz von EF 1070 ≡ 1 (mod 71).
Wenn ich nun m := 10100 mod 70 definiere, dann kann ich 10100 ersetzen durch 70 k + m (mit einem irrsinnig großen k \in \Bbb{Z}) und schreiben:
1010^100 = 1070 k + m = 1070 k · 10m
Wegen der eingangs begründeten Kongruenz 1070 ≡ 1 wissen wir aber auch, dass 1070 k ≡ 1 ist für alle k, und das macht den Wert von k für uns völlig irrelevant (tatsächlich kennen wir ihn ungefähr: k ≈ 1.42857 · 1098. Ein Riesenproblem hätten wir erst, wenn wir ihn genau kennen müssten.)
Daraus folgt die Behauptung 1010^100 ≡ 10m (mod 71).
That’s all 
Gruß
Martin
Genial, tausend dank