Mathe

Ich soll zeigen, dass es genau dann ein mult. Inverses von a € Z_n (mod n) gibt, wenn ggT(a, n) = 1:

a) ggT(a, n) = 1 => Ea' : a*a' = 1 (mod n)
a != 1
wenn man a^x (x=1..n-1) betrachtet, kann keines kongruent 0 sein, weil ggt(a,n)=1
jetzt müsste man noch zeigen, dass die a^x paarweise verschieden sind, weil sie dann die Menge {1,...n-1} bilden würden und somit ein Inverses gefunden wäre. Aber wie?

Jester

Es gibt zwei Moeglichkeiten:

Du zeigst, dass die Potenzabbildung injektiv ist mit x von 1...n, daraus folgt dann wegen Endlichkeit der Menge auch surjektivitaet. => irgendeine Potenz ist e, damit ist es invertierbar.
Du nimmst den euklidischen Algortihmus, der sagt:

a,n teilerfremd => es ex. r,s: r*a+s*n=1 dann rechnest Du mod n uns siehe da:
es wird yu r*a=1 wie gewuenscht ist also die Restklasse von r mod n die Inverse, die laut Euklid also existiert

MfG Jester

Original erstellt von Jester:
1) Du zeigst, dass die Potenzabbildung injektiv ist mit x von 1...n, daraus folgt dann wegen Endlichkeit der Menge auch surjektivitaet. => irgendeine Potenz ist e, damit ist es invertierbar.

fällt aus, weil ich nichts vorraussetzen will. Kannst du mir noch einen Tipp zu 1) geben?

Jester

Ich fürchte 1) war ein Schnellschuß. Zumindest wird es damit sehr schwierig.

zu 2):
Irgendwas mußt Du ja voraussetzen, in diesem Fall: ggT(a,n)=1. Daraus folgt auch schon alles. Das mit dem Euklid hab ich nur nochmal dazu geschrieben, weil der Dir die Zahlen r und s liefert. Lies einfach nochmal was drüber. Ist recht elementar, der hat sich nämlich noch nicht mit Gruppen beschäftigt

Jo, den XGCD kenn ich auch, aber ich wollte nur die Existenz irgendwie beweisen, ohne das Inverse tatsächlich auch anzugeben. Außerdem brauche ich noch b) ggT(a,n)!= 1 => es existiert nicht zu jedem a ein a' mit a*a'=1 (mod n)

Jester

Kannst Du doch genau so zeigen. Bzw. hab ich oben getan. Brauchst ja die Zahl nicht ausrechnen. Kannst ja ganz einfach sagen: dieses r ex. damit ist die Existenz bewiesen.

Zur b), da würd ich mir an Deiner Stelle mal überlegen, mit was(!=0 mod n) man es multiplizieren könnte, so das 0 (mod n) rauskommt. Und dann überlegste Dir, warum Nullteiler nicht invertierbar sein können.

Viel Erfolg!
MfG Jester