Inverses Element einer Gruppe

Question

Aufgabe:

Berechne mit Hilfe des erweiterten euklidischen Algorithmus sowohl ggT (15,109) als auch das Inverse von e = 15 in der multiplikativen Gruppe (Z*₁₀₉, * ₁₀₉)

(Hinweis: Es ist a * ₁₀₉ b = Rest (a*b,109) für zwei Zahlen a,b ∈ ℤ

Problem/Ansatz:

Errweiterter Euklidischer Algorithmus aufgestellt. Es kam heraus, dass der ggT = 1 ist., weil

109 * 4 + (-29) * 15 = 1.

4 und (-29) sind s4 und t4.

Wie berechnet man daraus das Inverse Element zu 15?

Answer 1

Das inverse Element von 15 ist -29 wegen

        -29·15 = -435 ≡ 1   mod 109.

Standardvertreter der Restklasse von -29 ist

        -29 + 109 = 80.

Comments

Danke oswald. Also versteh ich das richtich, dass -29 das inverse Element ist, weil -29 * 15 = -435 und der Rest zum nächsten Vielfachen von 109, nämlich 436, genau 1 beträgt. (weil 1 der ggT ist). Wäre der ggT jetzt trölf, müsste man dann eine Zahl nehmen, deren Rest zu einem Vielfachen von 109 genau trölf beträgt.

---

und der Rest zum nächsten Vielfachen von 109, nämlich 436

Das nächstkleinere Vielfache von 109 ist -436.

Wäre der ggT jetzt trölf

Wenn ggT(a,b) ≠ 1 ist, dann ist (ℤ*_b, ·_b) keine Gruppe. Dann hat a eventuell kein multiplikatives Inverses.

Beispiel. Multiplikationstafel für b=4 ist:

·b	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

Wie man sieht ist

        2 ·₄ x ≠ 1

für jedes x. Stattdessen ist 2 ein sogenannter Nullteiler, weil

        2 ·₄ x = 0

für ein x≠0 ist. Grund ist ggT(2,4) ≠ 1.

---

Es geht um ℤ*_b, nicht um ℤ_b.

---

@Spacko Möchtest du mich damit auf einen Fehler in meiner Argumentation hinweisen? Dann musst du mir etwas deutlicher auf die Sprünge helfen.

---

Ich fand die Argumentation von oswald eigentlich ganz schlüssig