Kleiner Satz von Fermat?
Wir wissen, dass der kleine Satz von Fermat für p prim und a eine natürliche Zahl gilt:
a^(p-1) = 1 mod p, falls a kein Vielfaches von p ist.
falls jedoch a^x = 1 mod p gilt, kann man daraus p-1|x folgern?
1 Antwort
Vom Beitragsersteller als hilfreich ausgezeichnet
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
lineare Algebra, Mathematik
Wenn man mit nur einem a "zufrieden" ist, dann geht das nicht:
7^3 = 343 = 1 mod 3, aber 2 teilt nicht 3.
Man muss also schon voraussetzen, dass a^x = 1 mod p für alle zu p teilerfremden a (wobei man a auf die Menge 1, ..., p-1 beschränken kann). Dann ist man in der zyklischen Gruppe Z/p*, und man kann tatsächlich p-1|x folgern, denn p-1 ist die Ordnung der Gruppe, also der kleinste Exponent x, der das leistet.