0 Daumen
1,9k Aufrufe

Aufgabe:

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

(Hinweis: Es ist a * 109 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?

von

1 Antwort

+1 Daumen
 
Beste Antwort

Das inverse Element von 15 ist -29 wegen

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

Standardvertreter der Restklasse von -29 ist

        -29 + 109 = 80.

von 105 k 🚀

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 ·4 x ≠ 1

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

        2 ·4 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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community