Rest von grossen Zahlen !

Neue Frage »

Ado Auf diesen Beitrag antworten »
Rest von grossen Zahlen !
Hallo ich sollte diese Aufgaben ausrechnen und später noch notieren ob es aus aus einer der beiden
Varianten des kleinen Satzes von Fermat folgt :



100^6 mod 7 = ?
10^5 mod 6 = ?
22^10 mod 11 = ?
94^31 mod 31 = ?
2^49 mod 50 = ?

Welche methode gibt es um den rest zu bestimmen verwirrt von so riesiegen Zahlen )

Das mit dem Fermat Satz , dass kann ich ja noch verstehen , doch wie ich die Werte hinbekomme :S ...

http://upload.wikimedia.org/math/3/f/6/3f6d98bcfb542e5933ff1589495fd3a2.png
Ich habe keinen Schimmer wo ich anfangen soll und wie ??
Bitte um hilfe !
sqrt4 Auf diesen Beitrag antworten »

Wenn a kein vielfaches von p ist, dann gilt


Das klappt schon mal sicher bei Aufgabe 1 (hier wäre also p=7 und a=100)

Die "Brute-Force" Methode wäre die Zahl schrittweise zu verkleinern.
Es ist
Also
Deshalb ist

In Übereinstimmung mit dem Ergebnis das der kleine Fermat liefert.
therisen Auf diesen Beitrag antworten »

Für die letzte Aufgabe genügt



(vgl. chinesischer Restsatz)


Gruß, therisen
Ado Auf diesen Beitrag antworten »

Danke für die schnelle und kompetente Antwort !
Neue Frage »
Antworten »



Verwandte Themen

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