Natürliche Zahlen/Ggt und kgV/Kommutativer Halbring/Aufgabe/Lösung

1. Die Kommutativität ist klar. Die ${}0$ ist das neutrale Element, da stets

   ${}{\operatorname {GgT} \,\left(a,0\right)}=a\,,$

   da ja jede Zahl die ${}0$ teilt und somit der größte Teiler von ${}a$ entscheidend ist, und bei ${}a=0$ der Wert des GgT nach Definition ${}0$ ist. Zum Nachweis der Assoziativität ist

   ${}{\operatorname {GgT} \,\left({\operatorname {GgT} \,\left(a,b\right)},c\right)}={\operatorname {GgT} \,\left(a,{\operatorname {GgT} \,\left(b,c\right)}\right)}\,$

   zu zeigen. Wenn eine der beteiligten Zahlen ${}0$ ist, so kommt links und rechts das gleiche heraus. Wir können also annehmen, dass alle Zahlen ungleich ${}0$ sind. Wenn die Zahlen durch ihre Primfaktorzerlegung gegeben sind, so ist der größte gemeinsame Teiler durch das Minimum der Exponenten gegeben. Da sich das Minimum assoziativ verhält, gilt auch für den GgT die Assoziativität.

2. Die Kommutativität ist klar. Die ${}1$ ist das neutrale Element, da stets

   ${}{\operatorname {KgV} \,\left(a,1\right)}=a\,,$

   da ja jede Zahl ein Vielfaches der ${}1$ ist. Zum Nachweis der Assoziativität ist

   ${}{\operatorname {KgV} \,\left({\operatorname {KgV} \,\left(a,b\right)},c\right)}={\operatorname {KgV} \,\left(a,{\operatorname {KgV} \,\left(b,c\right)}\right)}\,$

   zu zeigen. Wenn eine der beteiligten Zahlen ${}0$ ist, so kommt links und rechts ${}0$ heraus, da ${}0$ das einzige Vielfache der ${}0$ ist. Wir können also annehmen, dass alle Zahlen ungleich ${}0$ sind. Wenn die Zahlen durch ihre Primfaktorzerlegung gegeben sind, so ist das kleinste gemeinsame Vielfache durch das Maximum der Exponenten gegeben. Da sich das Maximum assoziativ verhält, gilt auch für das KgV die Assoziativität.

3. Es ist

   ${}{\operatorname {KgV} \,\left(a,{\operatorname {GgT} \,\left(b,c\right)}\right)}={\operatorname {GgT} \,\left({\operatorname {KgV} \,\left(a,b\right)},{\operatorname {KgV} \,\left(a,c\right)}\right)}\,$

   zu zeigen. Bei ${}a=0$ steht beidseitig ${}0$, da das KgV der ${}0$ mit einer beliebigen Zahl stets ${}0$ ist. Bei ${}b=0$ (analog $c=0$) ergibt sich beidseitig ${}{\operatorname {KgV} \,\left(a,c\right)}$. Wir können also annehmen, dass alle Zahlen ungleich ${}0$ sind. Da sowohl das GgT als auch das KgV aus der Primfaktorzerlegung ablesbar sind, können wir uns auf einen einzigen Primfaktor beschränken. Sei

   ${}a=p^{k}\,,$

   ${}b=p^{m}\,$

   und

   ${}c=p^{n}\,.$

   Dann ist

   ${}\operatorname {max} (k,\operatorname {min} (m,n))=\operatorname {min} (\operatorname {max} (k,m),\operatorname {max} (k,n))\,$

   zu zeigen. Da die Aussage symmetrisch in ${}m$ und ${}n$ ist, können wir

   ${}m\leq n\,$

   annehmen. Dann steht links das Maximum von ${}k$ und ${}m$ und rechts ist jedenfalls

   ${}\operatorname {max} (k,m)\leq \operatorname {max} (k,n)\,,$

   so dass das Minimum davon ebenfalls das Maximum von ${}k$ und ${}m$ ist.

Zur gelösten Aufgabe