Wie kann ich den Rest von 21^30 mod 20 mit einem Taschenrechner ausrechnen?

... komplette Frage anzeigen

5 Antworten

Dazu brauchts keinen Taschenrechner. Es gibt da Regeln, wie man das rechnet. Eine davon ist a ≡ b mod m => a^n ≡ b^n mod m. a=21, b=1, n=30 und m=20:  

21 ≡ 1 mod 20 (stimmt, also folgt) 21^30 ≡ 1^30 mod 20 und somit (da 1^30=1) 21^30 ≡ 1 mod 20

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von gerdax86
27.01.2016, 23:34

Danke, vor guten 20 Jahren wusste ich das bestimmt auch mal. Langsam dämmert es wieder. Könntest du mir noch bitte zur Hilfe einen Lösungsansatz für z.B 2^384 mod 20 geben?

0

Versuch´s mal so :

21^30  =  ( 20 + 1 )^30

Ich hoffe, Du hast schon Ahnung von Binomialkoeffizienten und kannst Dir die Summe zumindest vorstellen:

( 20 + 1 )^30 = 20^30 + a * 20^29 + b * 20^28 + c * 20^27 + .....

Alle Potenzen von 20 interessieren ja nicht  mod20 , deshalb schaust Du an das Ende der Summe, immer nach Potenzen geordnet:

....... + y * 20^2 + z * 20^1 + 1

Brauchst Du jetzt noch einen Taschenrechner ???

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Roach5
27.01.2016, 22:51

Diese Antwort ist sehr gut, wozu Taschenrechner wenn man Köpfchen gebrauchen kann. Ich wette der Taschenrechner ist "dumm" und wird das Ergebnis garnicht richtig ausrechnen, weil er erst versuchen wird, 21^30 auszurechnen, was viel zu groß ist.

Wenn du die Modulo-Rechengesetze bereits kennst (wenn du also algebraisch bewiesen hast, dass wir hier wirklich einen Ring haben), dann schreibst du einfach:

[21]^30 = [1]^30 = [1^30] = [1], alles mod 20, und bist fertig.

LG

3

Gar nicht, denn dazu müsste dein Taschenrechner mit 40 signifikanten Zahlenstellen rechnen können um den Modulo zufriedenstellend ausrechnen zu können. Die meisten Taschenrechnergeräte rechnen aber nur mit 10 Zahlenstellen. Wenn es da noch eine andere Möglichkeit gibt, so kenne ich sie nicht.

Antwort bewerten Vielen Dank für Deine Bewertung

Indem du einen guten Taschenrechner nimmst. Zum Beispiel diesen hier:
http://www.wolframalpha.com/input/?i=21%C2%B3%E2%81%B0+mod+20

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von YStoll
27.01.2016, 22:26

Alternativ schreibst du 21^(30) um zu (21²)^(15) = ((20 + 1)²)^(15) = (20 * 20 + 2 * 20 + 1)^(15) = (22 * 20 +1)^(15).

Hast du jetzt eine eigene Idee, wie man weiter rechnen kann?

0

Jeder gute Rechner kennt die PowMod-Funktion, die ohne die ultra extrem großen Zwischenergebnisse auskommt.

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

kann das mit 60 stelligen Zahlen. Diesen Rechner kann man per Handy aufrufen und ist so flexibler als jeder Taschenrechner -> Bild 1

Wie dieser Algorithmus funktioniert zeigt der Iterationsrechner im Beispiel 122:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm

Einfach Variablen a, b und c anpassen -> Bild 2

(mod ist in vielen Sprachen das % Zeichen)

Die 5 Schritte in Deinem Beispiel kann man fast schon im Kopf...

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?