0 Daumen
2,5k Aufrufe

Aloha-olah. Heißt "Hallo" und "Auf Wiedersehen" in Hawaii. Aber das hat nichts mit der folgenden Aufgabe zu tun, um die es jetzt geht

Berechne Rest (357, 17).

Das Endergebnis ist laut Python-Rechner 14.

Ansatz wäre bisher

Rest ( (33)19, 17).

Wir wissen nicht, wie das berechnet wird, bzw. welche Regeln man am geschicktesten anwendet.

Liebe Grüße,

Marceline The Vampire Queen

Avatar von

Tipp: Berechne mal mit deinem Rechner

Rest (3^{40}, 17) und Rest (3^{41}, 17).

2 Antworten

+1 Daumen
 
Beste Antwort

Nach dem kleinen fermatschen Satz ist 357 ≡ 316·3+9 ≡ 39 ≡ 14 mod 17.

Avatar von

Wie erkennt man allerdings schnell das 3^16 mod 17 = 1 ist ?

Über eine Wertetabelle hätte ich 3^8 mod 17 = -1 zuerst gefunden.

Gibt es da einen Trick sowas noch schneller zu erkennen?

Das gilt nach besagtem Satz.

Und wie geht die Rest(927 , 55) ? da komme ich leider nicht weiter..


Was natürlich geht allerdings sehr zeitaufwenig ist ist das runterbrechen auf einzelne Faktoren

9^27 mod 55
= 9·9^26 mod 55
= 9·81^13 mod 55
= 9·26^13 mod 55
= 9·26·26^12 mod 55
= 9·26·676^6 mod 55
= 9·26·16^6 mod 55
= 9·26·256^3 mod 55
= 9·26·36^3 mod 55
= 9·26·36·36^2 mod 55
= 9·26·36·1296 mod 55
= 9·26·36·31 mod 55
= 234·1116 mod 55
= 14·16 mod 55
= 224 mod 55
4

Ich hoffe aber Spacko hat auch hier einen geschickteren Ansatz.

Und wie geht die Rest(927 , 55) ? da komme ich leider nicht weiter..

Betrachte den Rest mod 5 ( der ist -1) und den Rest mod 11.

Da $$9\equiv\; -2\; mod \;11$$

gilt, ist

$$9^5\equiv\; (-2)^5\; \equiv\;(-32)\equiv\;1 \;mod \;11$$

Damit solltest du auf kurzen Wege zum Rest von

$$9^{25} \;mod \;11$$ kommen und den Schritt bis $$9^{27} $$ auch noch schaffen. 

Warum darf man das genau so machen

22 mod 11 = 0

22 mod 5 = 2

22 mod 55 = 22

Weißt du da etwas wo ich die Grundlagen nachlesen kann?

Weißt du da etwas wo ich die Grundlagen nachlesen kann?

Mist.

Ich wollte gerade die Broschüre "Korrespondenzzirkel Mathematik - Arbeitsmaterial für Klasse 7" hochladen, aber pdf-Dateien werden als Anhang nicht akzeptiert.

Deshalb hier nur ein Screenshot der Seite 15:

Unbenannt.JPG

Danke für die Antworten.


@Der Mathe_coach: Ich verstehe eine Umschreibung nicht:

= 9·8113 mod 55
= 9·2613 mod 55

8113 und 2613 sind doch nicht gleich.


@ abakus: Wie kommst du auf 22? Ich verstehe dass du 55 aufsplittest auf 5 und 11. Aber warum

9 = - 2 mod 11 ?

Wir müssen die Aufgaben ohne Taschenrechner rechnen. Also können nicht mal eben so 93 berechnen, ohne es umzuformen.

@Der Mathe_coach: Ich verstehe eine Umschreibung nicht:

a^b mod m = (a mod m)^b mod m

Du kannst den Modulo also bereits auf alle Faktoren anwenden.

@ abakus: Wie kommst du auf 22? Ich verstehe dass du 55 aufsplittest auf 5 und 11. Aber warum

9 ≡ -2 mod 11 weil
-2 + 11 = 9

Der Rest 9 ist also auch Gleichbedeutend mit einem Rest von -2. Wenn ich nämlich einmal 11 mehr subtrahiere.

Deshalb hier nur ein Screenshot der Seite 15

Vielen lieben Dank erstmal dafür. Die Sätze darauf kannte ich bereits.

Ich muss mir da mal Gedanken drüber machen wie ich aus dem Modula von a und dem Modulo von b mir den Modulo von a*b herausbekomme.

Das hat ja offensichtlich mit dieser Zeile zu tun.

blob.png

Ich werde da morgen mal drüber nachdenken.

0 Daumen

Das sind keine hohen, sondern winzige Potenzen.

Ein einfachen Algorithmus aus 3 Zeilen für diese Pow-Mod-Funktion findet man unter

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

ItPow.png

Nach 5 Schritten ist b<1 und das Ergebnis in b=aC[d+1]=aC[d]%c; also 14.

Das kann man noch weiter steigern und sich die PowPowMod(x,y,z,h) unter

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

mit richtig großen Zahlen ausrechnen lassen. (suche Funktion PowPowMod )

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community