wenn d a teilt und d b teilt, dann teilt d den ggT(a,b)

Question

Hey Ihr ! 

Kann mir bitte wer dabei helfen zu beweisen, dass wenn d a teilt und d b teilt, dann teilt d den ggT(a,b)

Ich hab versucht einen indirekten Beweis zu führen indem ich sage:

d teilt nicht ggT(a,b) ⇒ d teilt nicht a ∨ d teilt nicht b

Dann sagte ich: 

Sei z = ggT(a,b) ⇒ z|a ∧ z|b

Daraus folgt es ex. ein y, sodass z*y = a ⇒ z = a/y  und es ex. ein x, sodass z*x = b ⇒ z = b/x

Setze ich nun in die Bedingung ein folgt: d teilt nicht b/x und d teilt nicht a/y

 Weiter weiß ich nicht mehr. Ich drehe mich die ganze Zeit im Kreis und komme zu keiner Conclusio. Ich bitte verzweifelt um Hilfe.

Comments

Ich brauche bitte ganz Hilfe!

---

Vielleicht so: Es existieren x,y ∈ ℤ mit a = d·x und b = d·y.
Aus ggT(a,b) = ggT(d·x,d·y) = d·ggT(x,y) folgt d|ggT(a,b).

Answer 1

Hallo Jamma,

x | y genau dann, wenn die PFZ  (Primfaktorzerlegung) von x nur Primfaktoren (PF) enthält, die in der PFZ von y in mindestens gleich großer Potenz vorkommen.

→

d enthält  in seiner PFZ nur PF, die in den PFZ von a bzw. von b jeweils mindestens in gleich großer Potenz (wie bei d) vorkommen.

ggT(a,b) enthält in seiner PFZ alle PF von a und von b in ihrer in deren PFZ kleinsten vorkommenden Potenz.

→     in der PFZ von ggT(a,b) kommen alle PF der PFZ von d in mindestens gleich großer Potenz vor. 

→     d | ggT(a,b) 

Gruß Wolfgang