kleiner fermatscher satz
-
Hallo,
ich hab mir gerade den artikel zum genannten thema auf http://en.wikipedia.org/wiki/Fermat's_little_theorem durch gelesen und dieser besagt, dass für die zweite formel a kein vielfaches von p sein darf. um das zu prüfen, muss man doch erst mal den ggT bilden, oder? also verschwendete rechenzeit, da man ja auch die erste formel nehmen könnte wo diese bedingung nicht gilt ?
noch eine andere frage dazu, kann a jede beliebige natürliche zahl sein oder muss da gelten: a < p ?danke schon mal
vario-500
-
vario-500 schrieb:
Hallo,
ich hab mir gerade den artikel zum genannten thema auf http://en.wikipedia.org/wiki/Fermat's_little_theorem durch gelesen und dieser besagt, dass für die zweite formel a kein vielfaches von p sein darf. um das zu prüfen, muss man doch erst mal den ggT bilden, oder?Nein. Vielleicht weiß man dies ja schon konstruktionsbedingt oder es ist ein Fall, in dem es trivial zu zeigen ist. Da p schon als Primzahl feststeht, ist falls 1 < a < p automatisch a zu p teilerfremd und bei a > p muss man nur gucken, ob p a teilt.
also verschwendete rechenzeit, da man ja auch die erste formel nehmen könnte wo diese bedingung nicht gilt ?
Wenn man aber die zweite Formulierung braucht?
noch eine andere frage dazu, kann a jede beliebige natürliche zahl sein oder muss da gelten: a < p ?
Wikipedia ist richtig genug, dass du darauf vertrauen kannst, dass die Voraussetzungen dort richtig wiedergegeben sind. Also keine Einschränkung.
