ggT mit doppelter Inklusion

Question

Aufgabe:

Weise nach, dass fur d = ggT(a, b) gilt, dass dZ = aZ + bZ.
Anleitung: Verwende die Definitionen der vorkommenden Größen und begründen Sie damit die
behauptete Gleichheit der Mengen dZ und aZ + bZ mittels sogenannter doppelter Inklusion. Dies bedeutet,
dass in zwei Schritten argumentiert werden soll:
• Im ersten Schritt weise nach, dass dZ ⊆ aZ + bZ, d.h., dass aus x ∈ dZ folgt, dass x ∈ aZ + bZ.
• Im zweiten Schritt weise nach, dass dZ ⊇ aZ + bZ, d.h., dass aus x ∈ aZ + bZ folgt, dass x ∈ dZ

Problem/Ansatz:

Mein Ansatz wäre d ∈ N ist ein ggT von a und, wenn d|b und d|a und für jeden Teiler t von a und b gilt, dass auch t|d.

Daraus folgt, dass der ggT existiert. a,b ∈ aZ + bZ = dZ. d|a und d|b und d sind Teiler von a und b.

Wie beweise ich das mit zwei Schritten bzw. mit doppelter Inklusion?
Ich würde mich sehr um Ansatzhilfen freuen!

LG
pharmacyl

Comments

Was bedeutet für Euch die Schreiweise aZ + bZ. einfach, dass da a*z1+b*z2 steht?

---

dZ = Alle Vielfachen vom ggT

Also alle Vielfachen von a und b sind dZ.

aZ =  Alle Vielfachen von a

bZ = Alle Vielfachen von b

Answer 1

weise nach, dass dZ ⊆ aZ + bZ

Sei $x \in d\mathbb{Z}$.

Sei $v\in \mathbb{Z}$ mit $x = vd$. Ein solches $v$ existiert laut Definition von $d\mathbb{Z}$.

Seien $p,q \in \mathbb{Z}$ mit $d = pa+qb$. Solche $p$ und $q$ existieren, weil sie wegen $d=\operatorname{ggT}(a,b)$ mit dem erweiterten euklidischen Algorithmus berechnet werden können.

Dann ist

        $x = vd = v(pa+qb) = (vp)a + (vq)b$.

Wegen $v\in \mathbb{Z}$ und $p\in \mathbb{Z}$ und weil $\mathbb{Z}$ ein Ring ist, ist $vp\in\mathbb{Z}$.

Wegen $vp\in\mathbb{Z}$ ist $(vp)a \in a\mathbb{Z}$.

Analog dazu ist $(vq)b \in b\mathbb{Z}$.

Also ist laut Defnition der Mengenaddition $(vp)a + (vq)b \in a\mathbb{Z} + b\mathbb{Z}$.

Also ist auch $x\in a\mathbb{Z} + b\mathbb{Z}$.

d ∈ N ist ein ggT von a

Der $\operatorname{ggT}$ wird üblicherweis von mindestens zwei Zahlen bestimmt.

Daraus folgt, dass der ggT existiert.

Wegen $1|a$ und $1|b$ für alle $a,b\in\mathbb{Z}$ existiert $\operatorname{ggT}(a,b)$ immer. Findet man keinen größeren gemeinsamen Teiler als $1$, dann ist halt $\operatorname{ggT}(a,b) = 1$. Du brachst deshalb nicht extra zu schlussfolgern, dass der $\operatorname{ggT}$ existiert.

Wie beweise ich das mit zwei Schritten bzw. mit doppelter Inklusion?

Der eine Schritt ist, dass du die Inklusion $d\mathbb{Z} \subseteq a\mathbb{Z} + b\mathbb{Z}$ zeigst.

Der andere Schritt ist, dass du die Inklusion $a\mathbb{Z} + b\mathbb{Z}\subseteq d\mathbb{Z}$ zeigst.

Den einen Schritt habe ich dir oben gezeigt. Zum anderen Schritt:

Sei $x\in a\mathbb{Z} + b\mathbb{Z}$.

Seien $p,q \in \mathbb{Z}$ mit $pa+qb = x$. Begründe warum solche $p$ und $q$ existieren.

Seien $r,s \in \mathbb{Z}$ mit $rd = a$ und $sd = b$. Begründe warum solche $r$ und $s$ existieren.

Begründe damit, warum $x\in d\mathbb{Z}$ ist.

Comments

Danke für deine Erklärung zum ersten Schritt!! :) Um zu zeigen, dass x aus dZ ist, würde ich die Eigenschaft des ggT benutzen.

d=ggT(a,b) und daraus folgt, dass x ∈ dZ ist und somit ist dZ eine Obermenge von aZ + bZ

Ist das soweit korrekt?

LG

---

d=ggT(a,b)

Ja, das steht so in der Aufgabenstellung.

und daraus folgt, dass x ∈ dZ

Mir ist nicht klar, wie du darauf kommst.

---

Ich dachte, das leitet sich so von der Eigenschaft des ggT ab?

---

Sei $x\in a\mathbb{Z} + b\mathbb{Z}$.

Seien $p,q \in \mathbb{Z}$ mit $pa+qb = x$. Begründe warum solche $p$ und $q$ existieren.

Solche p und q existieren, weil jedes Vielfache von a und jedes Vielfache von b ein Vielfaches vom ggT ist?

Analog auch für r und s.

---

Ich denke ich verstehe deinen Ansatz:

x=pa+qb

rd = a

sd = b

x = p*rd + q *sd

oder?

---

Mir ist nicht klar, welche Eigenschaft des ggT du meinst.

Wie kann ich $x$ mittels $p$, $q$, $r$, $s$ und $d$ zusammenbauen?

---

Eigenschaft des ggT:
ggT(a, b) = ggT(a, b − qa) für alle q ∈ Z.

Indem ich sage alle Vielfachen von a und alle Vielfachen von b sind in der Menge des ggT enthalten

---

Alles klar.. Ich gebe es auf, ich weiß nicht wie ich genau auf die Lösung komme. Bin mit meinen Ansätzen wohl auf dem Holzweg

---

x = p*rd + q *sd

Genau so sieht's aus.

Jetzt d ausklammern liefert

        x = (pr+qs)d

Wegen pr+qs ∈ ℤ ist x ein ganzzahliges Vielfaches von d, also ist x ∈ dℤ.

---

Vielen Dank für deine Hilfe!!