Beweis: Wenn c | a und c | b folgt c | ggT(a,b)

Question

habe den Beweis wie folgt geführt:

$$c | a \Rightarrow a = x_1 \cdot c, x_1 \in \mathbb{Z}$$

$$c | b \Rightarrow b = x_2 \cdot c, x_2 \in \mathbb{Z}$$

Also wenn c | a, kann a als Vielfaches von c dargestellt werden. Und wenn c | b, kann auch b als Vielfaches von c dargestellt werden.

Weiterhin:

$$n = ggT(a,b) \Rightarrow a = x_3 \cdot n \land b = x_4 \cdot n$$

Also wenn n der ggT(a,b) ist, lässt sich a als Vielfaches von n und b als Vielfaches von n darstellen.

$$\Rightarrow n = \frac{a}{x_3} = \frac{x_1 \cdot c}{x_3} = c \cdot \frac{x_1}{x_3}$$

Also teilt c auch ggT(a,b).

Ist der Beweis korrekt?

Danke,

Thilo

Answer 1

n = c * x1 / x3

Ich denke nicht das das so gültig ist oder? Du hast damit ja nicht gezeigt dass x1/x3 ganzzahlig ist.

Comments

Also wenn ich voraussetze, dass $$ggT(ma, mb) = |m| \cdot ggT(a,b)$$ (eine Rechenregel für den ggT https://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_Gemeinsamer_Teiler) ist es ja leicht:

$$c | a \Rightarrow a = x_1 \cdot c, c | b \Rightarrow b = x_2 \cdot c$$

$$ggT(a,b) = ggT(x_1 \cdot c, x_2 \cdot c) = |c| \cdot ggT(x_1, x_2)$$

ist natürlich auch durch c teilbar.

Die Rechenregel ist nicht soo leicht zu beweisen, aber das reicht mir jetzt auch :P