{ (ik) mod n I k Element N } = Zn i,n sind tei

[Ionel_c07017]

Hallo leute, ich habe die aufgabe zu zeigen bzw zu widerlegen:

{(ik) mod n | k Element N }=Z_n i,n sind teilerfremnd

ich stehe jetzt echt vollkommen auf dem schlauch ich weiß nichtmal richtig um was es geht, wie ich anfangen soll. das einzige was ich weiß das es iwas mit der Gruppenthematik zutun hat. Ich hoffe ihr könnt mir weiterhelfen oder wenigstens ein paar anhaltspunkte geben.

danke schonmal im vorraus

lg

[Lutz_Lehmann]

Hi,

siehe erweiterter euklidischer Algorithmus. Wichtig ist, dass Du als Produkt mod n die 1 erreichen kannst. Das kann man z.B. als äquivalente Zwischeneigenschaft nehmen. Es gibt also ein k, so dass

ik=1 mod n

gilt. Nach Teilbarkeit gibt es also auch einen Faktor m mit

(ik-1)=mn

oder umgestellt

ik+(-m)n=1.

Das ist die Bezout-Identität, die die ggT-aussage liefert.

Gruß Lutz