Letzte Dezimalstellen einer Zahl berechnen

Neue Frage »

Matheneuling1991 Auf diesen Beitrag antworten »
Letzte Dezimalstellen einer Zahl berechnen
Gegeben sei die größte Mersenne Primzahl, also

, gesucht sind die letzten 2 Dezimalstellen. Nun ist das natürlich äquivalent dem Ergebnis, wenn ich die Zahl modulo 100 rechne;
Ich kann auch betrachten und am Schluss das Ergebnis einfach -1 rechnen..
Das heißt ich will

berechnen. Nun ist aber das Problem, wie ich das mache. Speziell interessiert mich die Version mit der eulerschen Phifunktion.
Kann mir das jemand das Prinzip davon erklären?
Danke!! smile

EDIT: Die Eulersche Phifunktion von 100 ist 40, aber ich kann nicht anwenden, dass 2^40=1(mod 100) ist, da 2 und 100 nicht teilerfremd sind... Gibt es eine Abwandlung des Satzes von Fermat, wie ich damit rechnen kann?
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

es ist vollkommen richtig, dass man den Satz von Euler-Fermat nicht direkt anwenden kann, da 2 und 100 teilerfremd sind.
Das Problem zu umgehen hilft- wie oft - der chinesissche Restsatz.
Matheneuling1991 Auf diesen Beitrag antworten »

Hey... smile
Danke für deine Antwort... Diesen Satz hatte ich, allerdings nur als Lösung von Aufgaben der Form:
Es gibt x Kugeln, mod 3 bleiben 2 übrig, mod 5 bleibt 1 übrig mod 7 bleiben 4 übrig...

So etwas in der Art... Wie wende ich das jetzt auf mein Problem an? Tut mir leid, dass ich den Zusammenhang da nicht sehe.. unglücklich
Captain Kirk Auf diesen Beitrag antworten »

Diese Variante/Folgerung des chin. Restsatzes ist durchaus die, die du hier brauchst. Halt nur die andere Richtung.
Betrachte dein Problem einmal mod 4 und einmal mod 25, dann kannst du die Lösung mod 100 wieder zusammenbasteln.
Matheneuling1991 Auf diesen Beitrag antworten »

Hm, du musst mir das wohl oder übel etwas genauer erklären... unglücklich
Ich muss praktisch den chinesischen Restsatz rückwärts anwenden, nur haben wir den erst gelernt, wodurch es mir wirklich an Übung fehlt..

Was ich mir auch überlegt habe: Nehmen wir mal an, ich möchte die Zahl mod 25 rechnen... Dann sind 25 und 2 teilerfremd und ich bekomme relativ leicht ein Ergebnis mod 25..
Dadurch kann ich die Antwort mod 100 auf 4 Zahlen eingrenzen..
(denn nehmen wir an, das Ergebnis sei 13, dann kann die Antwort mod 100 13, 38,63,88 sein
Die Zahl mod 4 kann ich auf diese Weise nicht rechnen, weil 2 und 4 nicht teilerfremd sind..

EDIT: Das zuvor war Schmarrn, da 7 ja nicht 100 teilt.. Aber wie mache ich jetzt weiter?

Mod 25 kam 2 heraus, also sind die zwei letzten Dezimalstellen entweder 02, 27, 52, oder 77
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Nehmen wir mal an, ich möchte die Zahl mod 25 rechnen.

Hat dir schon mal jemand von " Probieren geht über studieren" erzählt?
Du willst das rechnen, also tu es auch.

Zitat:
Dadurch kann ich die Antwort mod 100 auf 4 Zahlen eingrenzen..
Richtig.

Zitat:
Die Zahl mod 4 kann ich auf diese Weise nicht rechnen, weil 2 und 4 nicht teilerfremd sind..
Das ist zum Einen absolut nicht überraschend, denn wenn es ginge könnte man Euler-Fermat direkt mod 100 anwenden. Zum anderen ist es völlig unnötig.
Das Ergebnis ist durch bloßes Hinsehen völlig offensichtlich, ohne irgendwelche Sätze.

Zitat:
Mod 25 kam 2 heraus,

Ähh, nein.
 
 
Matheneuling1991 Auf diesen Beitrag antworten »

Mod 25 dürfte 2 schon stimmen...
Aber ich habe jetzt verstanden, was du willst, deswegen ein neuer Versuch

Definiere ; Gesucht ist diese Zahl mod 100;

Wir rechnen p* mod 25; Dies ergibt 2, also ist p* aus (2,27,52,77) mod 100

Nun ist p* offensichtlich ein Vielfaches von 4 und damit = 0 mod(4)... Und da nur 52 = 0 (mod 4) ist, ist 52 die gesuchte Zahl für p* bzw. 51 für p..

Die zwei letzten Dezimalzahlen sind daher 5... Passt das so?
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Mod 25 dürfte 2 schon stimmen...

Bitte teile vorher mit, wenn der besprochene Gegenstand sich ändert nicht nachher.
Es geht hier um das Ding, dass du p nennst.
Um vorletzten Post sprachst du anscheinend von der Zahl p*, ohne es mitzuteilen.
Ich kann leider nicht hellsehen.

Die Rechnung ist jetzt richtig, den Satz(?)
Zitat:
Die zwei letzten Dezimalzahlen sind daher 5...
versteh ich nicht.
Matheneuling1991 Auf diesen Beitrag antworten »

51 sorry... smile

Keine Ahnung, ich dachte, das wäre im ersten Post deutlich geworden... Jedenfalls vielen Dank!! smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »