07 Die ganzen Zahlen II

0:00 ...

Auf das Video Klicken zum Abspielen & Im Video ziehen zum Vor-/Zurückspielen

Timestamps

Daten werden geladen...

Die ganzen Zahlen II - Aufgabe 1 (von 3)

Der größte gemeinsame Teiler zweier natürlicher Zahlen $m$ und $n$ ist die größte natürliche Zahl $g$ mit der folgenden Eigenschaft: Es gibt natürliche Zahlen $m^{'}$ und $n^{'}$ mit $m = g \cdot m^{'}$ und $n = g \cdot n^{'}$ . Man schreibt $\begin{array}{r} g = g g T (m, n) . \end{array}$ Das kleinste gemeinsame Vielfache zweier natürlicher Zahlen $m$ und $n$ ist die kleinste natürliche Zahl $v$ mit der folgenden Eigenschaft: Es gibt natürliche Zahlen $m^{'}$ und $n^{'}$ mit $v = m \cdot m^{'}$ und $v = n \cdot n^{'}$ . Man schreibt $\begin{array}{r} v = k g V (m, n) . \end{array}$ Versuchen Sie, mithilfe der eindeutigen Primfaktorzerlegung der Zahlen $m$ und $n$ je ein Verfahren anzugeben, nachdem der ggT und der kgV bestimmt werden kann. Beachten Sie die Symmetrie der beiden Verfahren.

Es seien $\begin{array}{r} m = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot . . . \cdot p_{r}^{e_{r}} \end{array}$ und $\begin{array}{r} n = q_{1}^{f_{1}} \cdot q_{2}^{f_{2}} \cdot . . . \cdot q_{s}^{f_{s}} \end{array}$ die beiden eindeutigen Zerlegungen in Primfaktoren. Die Reihenfolge der Faktoren sei so eingerichtet, dass bis zu einem Index $t \geq 0$ die Primzahlen $p$ und $q$ übereinstimmen: $\begin{array}{r} p_{i} = q_{i} f \ddot{u} r a l l e 1 \leq i \leq t . \end{array}$ Der Fall, dass es gar keine gemeinsamen Primfaktoren gibt, ist durch $t = 0$ abgedeckt. Es gilt nun offenbar $\begin{array}{r} g g T (m, n) = p_{1}^{x_{1}} \cdot p_{2}^{x_{2}} \cdot . . . \cdot p_{" t "}^{x_{t}}, \end{array}$ wobei $x_{i}$ jeweils der kleinere der beiden Exponenten $e_{i}$ und $f_{i}$ ist.
Der ggT besteht also aus den gemeinsamen Primfaktoren, versehen mit den jeweils kleineren Exponenten.
Analog dazu ist $\begin{array}{r} k g V (m, n) = p_{1}^{y_{1}} \cdot p_{2}^{y_{2}} \cdot . . . \cdot p_{t}^{y_{t}} \cdot p_{t + 1}^{e_{t + 1}} \cdot p_{r}^{e_{r}} \cdot q_{t + 1}^{f_{t + 1}} \cdot . . . \cdot q_{s}^{f_{s}} \end{array}$ wobei $y$ , jeweils der größere der beiden Exponenten $e_{i}$ und $f_{i}$ ist. Der kgV besteht also aus allen überhaupt vorkommenden Primfaktoren, versehen mit den jeweils größeren Exponenten.

Die ganzen Zahlen II - Aufgabe 2 (von 3)

Beweisen Sie: Wenn für zwei natürliche Zahlen $m, n > 0$ $\begin{array}{r} g g T (m, n) = 1 \end{array}$ ist, dann gilt $k g V (m, n) = m n$ . Wie steht es mit der Umkehrung?

Nach der vorhergehenden Aufgabe ist das ganz einfach: $g g T (m, n) = 1$ bedeutet, die beiden Zahlen sind teilerfremd, es gibt also keine gemeinsamen Primfaktoren (setzen Sie $t = 0$ in der vorigen Aufgabe). Dann ist der kgV natürlich das Produkt der beiden Zahlen. Die Umkehrung gilt natürlich auch. Wenn für die Bildung des kgV das volle Produkt der beiden Zahlen nötig ist, dann ist das eben nur dann der Fall, wenn es keine gemeinsamen Primfaktoren gibt, der ggT also gleich $1$ ist.

Die ganzen Zahlen II - Aufgabe 3 (von 3)

Bereits im antiken Griechenland hat Euklid den vielleicht ersten zahlentheoretischen Algorithmus entdeckt. Sein Verfahren eignet sich, um den ggT zweier natürlicher Zahlen zu bestimmen. Gegeben seien also zwei natürliche Zahlen $m, n > 0 .$ Zeigen Sie, dass folgendes Vorgehen immer zum Ziel führt:

1. EINGABE $m, n > 0 .$
2. Falls $m = n$ ist, dann gib $m$ aus - ENDE.
3. Falls ist, vertausche die Zahlen $m$ und $n$ .
4. Ersetze $n$ durch $n - m$ und gehe zu Schritt 2.

Hinweis: Es ist nützlich, sich klar zu machen, dass $g g T (m, n) = g g T (m, n - m)$ ist, falls $n > m$ ist.

Da die Zahlen immer strikt verkleinert werden und $\geq 0$ bleiben, kommt der Algorithmus irgendwann immer zu $m = n$ und damit in der zweiten Zeile zu einem Ergebnis.
Klarerweise wird das Ergebnis durch die zweite und die dritte Zeile nicht verändert. Wir müssen noch zeigen, dass es auch durch die vierte Zeile nicht verändern wird. Dazu zeigen wir, dass stets $g g T (m, n) = g g T (m, n - m)$ ist, falls $n > m$ ist.
Wir zeigen noch mehr, nämlich dass die Menge $M_{1}$ aller gemeinsamen Teiler von $m$ und $n$ gleich der Menge $M_{2}$ aller gemeinsamen Teilen von $n - m$ ist.
$M_{1} \subseteq M_{2} :$ Es sei $t \in M_{1} .$ Dann gibt es natürliche Zahlen $k_{1}$ und $k_{2}$ mit $\begin{array}{r} m = k_{1} \cdot t u n d n = k_{2} \cdot t . \end{array}$ Dann ist $\begin{array}{r} n - m = k_{1} \cdot t - k_{2} \cdot t = (k_{1} - k_{2}) \cdot t \end{array}$ und damit $t \in M_{2}$ .

$M_{2} \subseteq M_{1} :$ Es sei $x \in M_{2}$ . Dann gibt es natürliche Zahlen $l_{1}$ und $l_{2}$ mit $\begin{array}{r} m = l_{1} \cdot x u n d n - m = l_{2} \cdot x . \end{array}$ Dann ist $\begin{array}{r} n = m + (n - m) = l_{1} \cdot x + l_{2} \cdot x = (l_{1} + l_{2}) \cdot x \end{array}$ und damit $x \in M_{1} .$

Fertig!