Beweis ggT(a · b, n) | ggT(a, n) · ggT(b, n)

Question

Ich soll ggT(a · b, n) | ggT(a, n) · ggT(b, n) beweisen.

bei jedem beliebigen Beispiel stimmt die Aussage .Wie verallgemeinere ich das nun?

bsp.: ggT(2*55,35) | ggT(2,35)* ggT (55,35) 

          5                     |     1         *   5             -> 5 teilt die 5 

Würde mich über einen Ansatz freuen :))

 

Answer 1

Hallo Tinaaa,

$\exists \alpha,\beta\in\mathbb{Z}:\alpha\cdot a+\beta\cdot n=ggT(a,n)$ und $\exists\gamma,\delta\in\mathbb{Z}:\gamma\cdot b+\delta\cdot n=ggT(b,n)$

Wir multiplizieren die beiden Gleichungen und erhalten:

$ab\cdot\alpha\gamma+n\cdot (\beta\gamma b+\alpha\delta a+\beta\delta n)=ggT(a,n)\cdot ggT(b,n)$

Jede Zahl, die $ab$ und $n$ teilt, teilt auch $ab\cdot\alpha\gamma+n\cdot (\beta\gamma b+\alpha\delta a+\beta\delta n)$ und demnach auch das Produkt $ggT(a,n)\cdot ggT(b,n)$. Insbesondere gilt dies auch für den $ggT$ von $ab$ und $n$, d.h. $ggT(ab,n)\mid ggT(a,n)\cdot ggT(b,n)$ $\Box$

André