Modulo mit hohen Potenzen |
03.12.2009, 15:45 | Zutui | Auf diesen Beitrag antworten » | ||
Modulo mit hohen Potenzen gilt. Wie geht man am besten vor? Mit der Aufteilung: kommen wir nicht weiter. Über Tipps wären wir dankbar!! Mfg |
||||
03.12.2009, 15:49 | howdy | Auf diesen Beitrag antworten » | ||
Schau dir mal den Satz von Euler-Fermat an Außerdem dürftest du dir das Square and Multiply mal anschauen. Damit kann man ganz gut hohe Potenzen ausrechnen, wenn das Anwenden von (Euler-)Fermat nicht ausreicht. |
||||
03.12.2009, 15:55 | Zutui | Auf diesen Beitrag antworten » | ||
zu Euler-Fermat stand bereits etwas im Lösungsansatz: Das würde dann ergeben müssen: wie aber kommt man auf die Zahlen 42 und 46, bzw. 43 und 47. Die kann man ja nicht raten *edit* zu Square and Multiply... ich hab die Rechnung bei http://www.csc81.de/html/projects/square...tiply/index.htm eingegeben... es kommt folgendes Ergebnis raus: |
||||
03.12.2009, 16:06 | howdy | Auf diesen Beitrag antworten » | ||
Die Anzahl zu n teilerfremden Zahlen in {0,1,...,n-1} wird bezeichnet. Die Funktion heißt Eulersche Phi-Funktion. Hat die Zahl n die kanonische Darstellung so kannst du berechnen mit Nun, 2021 hat die Kanonische Darstellung 43*47. Das Lemma von Fermat sagt, dass Mit Anwendung der Potenzgesetze und den Homomorphieregeln beim Rechnen mit Modulo geht das in dem Spezielfall natürlich auch. Lustigerweise ist Edit: Fehler korrigiert und ergänzt |
||||
03.12.2009, 16:25 | Zutui | Auf diesen Beitrag antworten » | ||
Nochmal zurück zu Da kommt man doch durch "Überlegung" drauf, oder? Ich suche ja Primzahlen, die miteinander multipliziert 2021 ergeben, richtig? Und warum kommt jetzt auf der Webseite raus? Das hatte ich nämlich bei meinem ersten zwei Lösungsansätzen auch raus |
||||
03.12.2009, 16:27 | MLRS | Auf diesen Beitrag antworten » | ||
...weil 47 offensichtlich nicht teilerfremd zu 2021 ist und Euler-Fermat gilt nur für |
||||
Anzeige | ||||
|
||||
03.12.2009, 16:32 | howdy | Auf diesen Beitrag antworten » | ||
Jap, hab auch gemerkt, dass ich da voreilig gesprochen habe |
||||
03.12.2009, 16:38 | Zutui | Auf diesen Beitrag antworten » | ||
also ist 517 richtig, oder? |
||||
03.12.2009, 16:42 | howdy | Auf diesen Beitrag antworten » | ||
Ja |
||||
03.12.2009, 16:48 | Zutui | Auf diesen Beitrag antworten » | ||
alles klar. Danke für die schnelle Hilfe! |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|