Kleiner Fermat Primzahltest

Question

Guten Tag ,

der kleine Fermat liefert für alle Basen die Restklasse 1 , wenn modul eine Primzahl ist

Ist der Modul keine Primzahl , liefert er für mache Basen ggt(basis,modul)==1 auch 1 , bei Carmichaelzahlen für alle.

Ich vermute,dass bei Basen ggt(basis,modul)<>1 das Ergebnis immer <> 1 erfolgt , habe aber leider keine Beweisidee.

Anders formuliert : Ist eine Carmichaelzahl beim Fermatprizahltest das "schlechteste Ergebnis" ?

Besten Dank

Herbert Wagner

Answer 1

wenn  der ggT(m, n) <> 1 ist, dann handelt es sich bei m (Basis) um einen Nullteiler im Ring Z/nZ, wenn n (Modul) die zu untersuchende Zahl ist. m ist dann nicht invertierbar in diesem Ring, mit anderen Worten existiert kein m^-1 in Z/nZ, sodass m*m^-1 = 1 (mod n). Das heißt auch, dass keine Potenz von m gleich 1 ist.

Ein Hinweis: Wenn ggT(m, n) <> 1 ist, dann ist die Zusammengesetztheit der Zahl n bereits gezeigt.

MfG

Mister