Modulo mit hohen Potenzen

Neue Frage »

Zutui Auf diesen Beitrag antworten »
Modulo mit hohen Potenzen
Weisen Sie nach, dass

gilt.


Wie geht man am besten vor?

Mit der Aufteilung:

kommen wir nicht weiter.

Über Tipps wären wir dankbar!!

Mfg
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.
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 Augenzwinkern


*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:

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
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 unglücklich
MLRS Auf diesen Beitrag antworten »

Zitat:
Original von Zutui
Und warum kommt jetzt auf der Webseite raus? Das hatte ich nämlich bei meinem ersten zwei Lösungsansätzen auch raus unglücklich


...weil 47 offensichtlich nicht teilerfremd zu 2021 ist Augenzwinkern

und Euler-Fermat gilt nur für
 
 
howdy Auf diesen Beitrag antworten »

Jap, hab auch gemerkt, dass ich da voreilig gesprochen habe smile
Zutui Auf diesen Beitrag antworten »

also ist 517 richtig, oder?
howdy Auf diesen Beitrag antworten »

Ja smile
Zutui Auf diesen Beitrag antworten »

alles klar.

Danke für die schnelle Hilfe!
Neue Frage »
Antworten »



Verwandte Themen

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