Fermat-Test mit ungeraden Exponenten (Primzahlen)

Erste Frage Aufrufe: 359     Aktiv: 22.10.2021 um 13:45
Jetzt Frage stellen
0
Moin in die Runde. Ich habe eine Frage zum Fermat-Test.
Wie gehe ich denn vor, wenn ich einen ungeraden Exponenten habe, also z.b. die 11 (Die ja nebenbei auch ne Primzahl ist)?
Habe mir die Zahl p=67 zur Überprüfung und die zufällige Zahl x=49 rausgesucht. Ggt ist 1, also betrachte ich ja x^p-1 mod p = 49^66 mod 67 Habe die jetzt bis auf 9^11 mod 67 runtergebrochen und hänge da jetzt fest.

Danke für eure Hilfe!
Diese Frage melden
gefragt

Student, Punkte: 12

 
Kommentar schreiben
1 Antwort
0

Wo ist denn das Problem? Willst Du ohne TR auskommen?

Du kannst noch weiter runterbrechen: $9^{11}=(9^2)^5\cdot 9\equiv 14^5\cdot 9=(14^2)^2\cdot 14\cdot 9$ usw. Die Frage ist, wann Du Dir den TR erlaubst.
Beachte, wenn am Ende 1 rauskommt, heißt das nicht, dass $p$ eine Primzahl ist.

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 39.14K

 
Danke für deine Antwort! Manchmal ist es so einfach, dass man die Lösung einfach nicht sieht.   ─   keavfly 22.10.2021 um 13:45

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.
Jetzt Antwort schreiben