Zeigen Sie mittels Division mit Rest, dass d sowohl a als auch b teilt.

Question

Seien a, b ∈ Z nicht beide gleich Null. Sei d die kleinste naturliche Zahl, für die  l, k ∈ Z existieren so, dass d = l · a + k · b.

1. Zeigen Sie mittels Division mit Rest, dass d sowohl a als auch b teilt.
2. Folgern Sie, dass d = ggT(a, b).

Answer 1

Sieht für mich nach dem erweiterten euklidischen Algorithmus aus, dürft ihr den verwenden?

Comments

ıch glaube ja, wir dürfen

---

Der erweiterte Euklidische Algorithmus (a,b) gibt aus:

ggT(a,b)=u*a+v*b

Dazu führst du zuerst den euklidischen Algorithmus aus, also:

a = q1*b + r1 (mit r1=a%b und q1=a/b ganzzahlige Division)

b = q2*r1 + r2 (mit r2=b%r1 und q2=b/r1 ganzzahlige Division)

...

$$r_{n-2}=q_{n}*r_{n-1} + r_{n} \\ r_{n-1}=q_{n+1}*r_{n} + 0$$

Dann ist rn dein ggT(a,b). und dann kannst du rückwärtseinsetzen (von der vorletzten Gleichung im euklidischen Algorithmus), also

$$r_n = r_{n-2}-q_{n}*r_{n-1}$$

und dann ersetzt du in der Gleichung von r_n-3: r_n-2 durch die Darstellung in der Zeile obendrüber. Bis du zur Darstellung gelangst:

r_n=u*a+v*b (=ggT(a,b))

---

Kannst du mit dieser auch helfen?

Beweisen Sie, dass [a] ein multiplikatives Inverses in Z_m hat, falls ggT(a, m) = 1.
Zu zeigen ist also:
ggT(a, m) = 1 ⇒ ∃ [b] ∈ Z_m : [a] · [b] = 1

---

ggt(a,m)=1 -> (Anwendung eeA) 1 = u*a + v*m, v*m ist in einer Restklasse m 0, also 1=u*a somit ist u Inverses von a