Ordnung auf primen Restsystemen
-
Hallo Leute,
ich versuche folgende Aussage zu beweisen:
\forall a \in Z^*_m : ord(a) \mbox{ teilt } \phi (m)
wobei:
das vollständige prime Restsystem mod m istund
ord(a) := min \{k \in N \; | \; a^k \equiv 1 \bmod m \}Es gilt dann aufgrund des kleinen Satzes von Fermat:
irgendwie finde ich keinen Ansatz dafür.
Vielleicht könnte mir jemand einen Ansatz geben...vielen Dank im Voraus!
Gruß mathik
-
Ansatz: $$a^{\mathrm{ord},a} = a^{\phi(m)} = 1$$. Minimalität von ord a.
-
dfgdfg schrieb:
Ansatz: $$a^{\mathrm{ord},a} = a^{\phi(m)} = 1$$. Minimalität von ord a.
so weit war ich auch schon....
vielleicht einen Ansatz, der etwas weiter geht?
-
Hi
Hab grad keine Lust auf Latex, sorry
Es gilt
a^phi(m) = 1 mod m
nach Satz von Euler und da (a,m)=1.Zeigen allgemein:
a^k = 1 mod m => ord(a) | kSei
k = l*ord(a) + r für ein 0<=r<ord(a)
=> 1 = a^k = a^(l*ord(a) + r) = a^(l*ord(a)) * a^r = a^r mod mDa aber r<ord(a) kann nur r=0 gelten
=> ord(a)|kspace
-
space schrieb:
Hi
Hab grad keine Lust auf Latex, sorry
Es gilt
a^phi(m) = 1 mod m
nach Satz von Euler und da (a,m)=1.Zeigen allgemein:
a^k = 1 mod m => ord(a) | kSei
k = l*ord(a) + r für ein 0<=r<ord(a)
=> 1 = a^k = a^(l*ord(a) + r) = a^(l*ord(a)) * a^r = a^r mod mDa aber r<ord(a) kann nur r=0 gelten
=> ord(a)|kspace
hey danke!
ist ja einfach. und ich hatte es irgendwie mit der multiplikativität von φ versucht...
mathik