Restklassen und multiplikatives Inverse

Question

Hallo zusammen. Ich versuche gerade das multiplikative Inverse zu erklären und bräuchte eure Meinung, ob dass was ich geschrieben habe gut ist. Vielen Dank für euer Feedbeek. Text: Eine Restklasse [a]m ∈ ℤm heißt multiplikativ invertierbar, falls es ein [b]m ∈ ℤm gibt, sodass [a]m ⋅ [b]m = [1]m gilt. [b]m ist damit das multiplikative Inverse von [a]m. Das multiplikative Inverse zu [a]m muss nicht immer existieren. Aber [a]m ∈ ℤm ist dann genau multiplikativ invertierbar, wenn a und m teilerfremd sind. Es gibt also eine Restklasse in der ein (äquivalent jeder) Repräsentant zu m teilerfremd ist. D.h. es gilt nach der Kongruenzgleichung: a ⋅ b ≡ 1 mod m, wenn der ggT(a, m) = 1 ist. Dazu muss man sagen, dass für das multiplikative Inverse nur der kleinste, nichtnegative Repräsentant der entsprechenden Restklasse angegeben wird.
Bei teilerfremden Restklassen spricht man auch von primen Restklassen. Die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im Restklassenring. Die Menge aller primen Restklassen modulo m wird mit ℤm* abgekürzt und bildet mit der Multiplikation die prime Restklassengruppe. Es gibt genau φ(n) invertierbare Elemente in ℤm, wobei φ die Euler’sche φ-Funktion ist.

Comments

Dazu muss man sagen, dass für das multiplikative Inverse nur der kleinste, nichtnegative Repräsentant der entsprechenden Restklasse angegeben wird.

Das verstehe ich nicht: ich kann doch von vornherein
das absolut kleinste Restsystem nehmen und meine Repräsentanten
von dort nehmen. Welche Repräsentanten ich nehme,
ist doch eine Frage einer Übereinkunft oder der Willkür.

---

Also ist das überflüssig. Der Rest ist aber doch verständlich oder ? Frage noch: Ist dieser Satz doppelt gemoppelt oder gut: "Es gibt also eine Restklasse in der ein (äquivalent jeder) Repräsentant zu m teilerfremd ist." Danke für eine Antwort.

---

Ich würde den Satz einfach weglassen.

---

Beide jetzt oder nur den wo du verwirrt bist.

---

Sorry! Ich meine nur den:

"Dazu muss man sagen, dass für das multiplikative Inverse nur der kleinste, nichtnegative Repräsentant der entsprechenden Restklasse angegeben wird."

---

Danke für deine rasche Antwort.

---

Ich wollte noch fragen, ob ich den satz von Euler-Fermat nicht auch so schreiben kann: a^φ(n) mod n = 1 mod n. Ist ja dasselbe wie a^φ(n) ≡ 1 mod n oder?

Answer 1

Ich finde es ganz gut, würde aber (s.u.) noch eine Begründung einschieben:

Eine Restklasse [a]m ∈ ℤm heißt multiplikativ invertierbar, falls es ein [b]m ∈ ℤm gibt, sodass [a]m ⋅ [b]m = [1]m gilt. [b]m ist damit das multiplikative Inverse von [a]m. Das multiplikative Inverse zu [a]m muss nicht immer existieren. Aber [a]m ∈ ℤm ist dann genau multiplikativ invertierbar, wenn a und m teilerfremd sind.

Dann würde ich noch einschieben:

Denn dann gilt ja nach dem erweiterten Euklid-Algorithmus:
Es gibt x,y ∈ ℤ mit a*x+y*m=1     ==>   a*x = 1 - y*m also a*x ≡ 1 mod(m).
Und x ist dann Repräsentant der in der Def. des Inversen angesprochenen Klasse [b].

Es gibt also eine Restklasse in der ein (äquivalent jeder) Repräsentant zu m teilerfremd ist. D.h. es gilt nach der Kongruenzgleichung: a ⋅ b ≡ 1 mod m, wenn der ggT(a, m) = 1 ist. Dazu muss man sagen, dass für das multiplikative Inverse nur der kleinste, nichtnegative Repräsentant der entsprechenden Restklasse angegeben wird.

Bei teilerfremden Restklassen spricht man auch von primen Restklassen. Die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im Restklassenring. Die Menge aller primen Restklassen modulo m wird mit ℤm* abgekürzt und bildet mit der Multiplikation die prime Restklassengruppe. Es gibt genau φ(n) invertierbare Elemente in ℤm, wobei φ die Euler’sche φ-Funktion ist.

Comments

Ist ann mein Absatz mit "Es gibt also eine Restklasse in der ein (äquivalent jeder) Repräsentant zu m teilerfremd ist. D.h. es gilt nach der Kongruenzgleichung: a ⋅ b ≡ 1 mod m, wenn der ggT(a, m) = 1 ist. Dazu muss man sagen, dass für das multiplikative Inverse nur der kleinste, nichtnegative Repräsentant der entsprechenden Restklasse angegeben wird." überflüssig oder kann ich den drinnen lassen?

---

Hier werden wieder einmal mehrere Foren gleichzeitig bemüht:

---

Was meinst du damit?

---

Also soll sollte mein Text jetzt lauten:

Eine Restklasse [a]m ∈ ℤm heißt multiplikativ invertierbar, falls es ein [b]m ∈ ℤm gibt, sodass [a]m ⋅ [b]m = [1]m gilt. [b]m ist damit das multiplikative Inverse von [a]m. Das multiplikative Inverse zu [a]m muss nicht immer existieren. Aber [a]m ∈ ℤm ist dann genau multiplikativ invertierbar, wenn a und m teilerfremd sind. Denn dann gilt nach dem erweiterten Euklid-Algorithmus:
Es gibt x,y ∈ ℤ mit a*x+y*m=1    ==>  a*x = 1 - y*m also a*x ≡ 1 mod(m).
Und x ist dann Repräsentant der in der Def. des Inversen angesprochenen Klasse [b]. Bei teilerfremden Restklassen spricht man auch von primen Restklassen. Die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im Restklassenring. Die Menge aller primen Restklassen modulo m wird mit ℤm* abgekürzt und bildet mit der Multiplikation die prime Restklassengruppe. Es gibt genau φ(n) invertierbare Elemente in ℤm, wobei φ die Euler’sche φ-Funktion ist.