Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der größte gemeinsame Teiler ( $\operatorname{ggT}$ ) und das kleinste gemeinsame Vielfache ( $\operatorname{kgV}$ ) sind zwei eng zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle.

Für zwei ganze Zahlen $m$ und $n$ , die nicht beide $0$ sind, gibt es stets einen größten gemeinsamen Teiler $\operatorname{ggT}(m, n)$ , d. h. die größte natürliche Zahl, durch die sowohl $m$ als auch $n$ ohne Rest teilbar sind. Sind $m$ und $n$ nicht null, so gibt es auch ein kleinstes gemeinsames Vielfaches $\operatorname{kgV}(m,n)$ , d. h. eine kleinste positive ganze Zahl, die sowohl Vielfaches von $m$ als auch Vielfaches von $n$ ist. Ist $m$ oder $n$ gleich null, so legt man $\operatorname{kgV}(m, n) = 0$ fest.

Insbesondere ist $\operatorname{ggT}(m,1)=1$ und $\operatorname{kgV}(m,1)=|m|$ sowie $\operatorname{ggT}(m,0)=|m|$ und $\operatorname{kgV}(m,0)=0$ .

Es gilt stets $|m \cdot n| = \operatorname{ggT}(m,n) \cdot \operatorname{kgV}(m, n)$ , also lässt sich jeweils das $\operatorname{kgV}$ aus dem $\operatorname{ggT}$ errechnen, und umgekehrt.

In der englischsprachigen internationalen Literatur wird der $\operatorname{ggT}$ mit $\operatorname{gcd}$ (greatest common divisor) und das $\operatorname{kgV}$ mit $\operatorname{lcm}$ (least common multiple) bezeichnet.

Inhaltsverzeichnis

1 Anwendung in der Bruchrechnung
2 Berechnung
- 2.1 Berechnung über die Primfaktorzerlegung
- 2.2 Berechnung durch den euklidschen Algorithmus
3 Berechnung des ggT und des kgV von mehreren Zahlen
4 Darstellung von ggT(m, n) aus m und n
5 Rechenregeln
6 kgV und ggT in weiteren algebraischen Strukturen
- 6.1 Beispiel

[Bearbeiten] Anwendung in der Bruchrechnung

Angenommen, wir möchten zwei Brüche addieren:

$\frac{17}{21} + \frac{44}{35}$

Dann wird man zuerst einen möglichst kleinen gemeinsamen Nenner der beiden Brüche suchen. Man kann natürlich der Einfachheit halber $21$ mit $35$ multiplizieren, was $735$ ergibt. Man kann aber auch das $\operatorname{kgV}$ von $21$ und $35$ berechnen, welches $105$ ist. Die beiden Brüche werden auf den Nenner $105$ erweitert:

$\frac{17}{21} + \frac{44}{35} = \frac{5 \cdot 17}{5 \cdot 21} + \frac{3 \cdot 44}{3 \cdot 35} = \frac{85 + 132}{105} = \frac{217}{105}$

Um Zähler und Nenner kleiner zu bekommen, bestimmt man den $\operatorname{ggT}$ von $217$ und $105$ , der $7$ beträgt. Damit lässt sich der Bruch durch $7$ kürzen:

$\frac{217}{105} = \frac{31 \cdot 7}{15 \cdot 7} = \frac{31}{15}$

[Bearbeiten] Berechnung

[Bearbeiten] Berechnung über die Primfaktorzerlegung

$\operatorname{ggT}$ und $\operatorname{kgV}$ kann man über die Primfaktorzerlegung (Faktorisierung) von a und b bestimmen. Ein Beispiel:

a = 3528 = 2³ · 3² · 5⁰ · 7²

b = 3780 = 2² · 3³ · 5¹ · 7¹

Für den $\operatorname{ggT}$ nimmt man die kleinsten Exponenten der zugehörigen Basen die in beiden Primfaktorzerlegungen vorkommen:

$\operatorname{ggT}$ (3528,3780) = 2² · 3² · 5⁰ · 7¹ = 252

Für das $\operatorname{kgV}$ verwendet man die größten Exponenten der jeweiligen Basen:

$\operatorname{kgV}$ (3528,3780) = 2³ · 3³ · 5¹ · 7² = 52.920

[Bearbeiten] Berechnung durch den euklidschen Algorithmus

Die Berechnung der Primfaktorzerlegung großer Zahlen und damit auch die Bestimmung des größten gemeinsamen Teilers bzw. des kleinsten gemeinsamen Vielfachen nach obiger Methode ist sehr aufwändig. Mit dem euklidschen Algorithmus existiert jedoch ein effizientes Verfahren, um den größten gemeinsamen Teiler zweier Zahlen zu berechnen. Dieses Verfahren wird durch den Steinschen Algorithmus noch weiter verbessert.

Mit Hilfe des größten gemeinsamen Teilers kann dann auch das kleinste gemeinsame Vielfache effizient berechnet werden:

$\operatorname{kgV}(m,n) = \frac{|m \cdot n|}{\operatorname{ggT}(m,n)}$

[Bearbeiten] Berechnung des ggT und des kgV von mehreren Zahlen

Der $\operatorname{ggT}$ und das $\operatorname{kgV}$ lassen sich von beliebig vielen Zahlen berechnen, da beide Abbildungen assoziativ sind:

$\operatorname{ggT}(m,\,\operatorname{ggT}(n,p)) = \operatorname{ggT}(\operatorname{ggT}(m,n),\,p) = \operatorname{ggT}(m,n,p)$

$\operatorname{kgV}(m,\,\operatorname{kgV}(n,p)) = \operatorname{kgV}(\operatorname{kgV}(m,n),\,p) = \operatorname{kgV}(m,n,p)$

[Bearbeiten] Darstellung von ggT(m, n) aus m und n

Hauptartikel: Erweiterter euklidischer Algorithmus.

Der $\operatorname{ggT}$ von $a$ und $b$ lässt sich als Linearkombination von $a$ und $b$ mit zwei ganzzahligen Koeffizienten $s$ und $t$ darstellen:

$\operatorname{ggT}(a,b)=sa+tb$

Die Koeffizienten $s$ und $t$ können mit einer Erweiterung des Euklidischen Algorithmus bestimmt werden. Nützlich ist dies z. B. bei der Berechnung von Inversen in Restklassenringen.

Beispiele:

$\operatorname{ggT}(12,18) = 6 = (-1)\cdot 12 + 1\cdot 18$
$\operatorname{ggT}(3,8) = 1 = (-5)\cdot 3 + 2\cdot 8$

[Bearbeiten] Rechenregeln

Für alle ganzen Zahlen $a$ und $b$ gilt:

$\operatorname{ggT}(a, b) = \operatorname{ggT}(b, a)$ Kommutativgesetz
$\operatorname{ggT}(-a, b) = \operatorname{ggT}(a, b)$
$\operatorname{ggT}(a, a) = |a|$
$\operatorname{ggT}(a, 0) = |a|$
$\operatorname{ggT}(a, 1) = 1$
$\operatorname{ggT}(a, b) = \operatorname{ggT}(b,a \;\bmod\; b)$
$\operatorname{ggT}(a, b) = \operatorname{ggT}(b,a-b)$

Ist zusätzlich $m$ eine natürliche Zahl, dann gilt:

$\operatorname{ggT}(m a, m b) = m \cdot\operatorname{ggT}(a, b)$ Distributivgesetz
$\operatorname{ggT}(a + m b, b) = \operatorname{ggT}(a, b)$

Ist $m$ ein gemeinsamer Teiler von $a$ und $b$ , dann gilt:

$\operatorname{ggT}(a/m, b/m) = \operatorname{ggT}(a, b)/m$

Der $\operatorname{ggT}$ ist in folgendem Sinne eine multiplikative Funktion: Sind $a$ und $b$ teilerfremd, dann ist

$\operatorname{ggT}(a b, m) = \operatorname{ggT}(a, m) \cdot\operatorname{ggT}(b, m)$

[Bearbeiten] kgV und ggT in weiteren algebraischen Strukturen

$\operatorname{kgV}$ und $\operatorname{ggT}$ lassen sich nicht nur für natürliche (und ganze) Zahlen definieren. Man kann sie z. B. auch für Polynome bilden. Statt der Primzahlzerlegung nimmt man hier die Zerlegung in irreduzible Faktoren:

f (x) = x 2 + 2 x y + y 2 = (x + y) 2

g (x) = x 2 - y 2 = (x + y)(x - y)

Dann ist $\operatorname{ggT}(f, g) = x + y$ und $\operatorname{kgV}(f, g) = (x + y)^2 (x - y)$ .

Möglich wird dies, da auch für Polynome eine Division mit Rest existiert.

Um den Begriff des größten gemeinsamen Teilers auf beliebige kommutative Ringe ausdehnen zu können, muss man die Definition ändern, da in beliebigen Ringen nicht vorausgesetzt werden kann, dass die Elemente bezüglich $<$ angeordnet werden können. Deshalb ersetzt man diese Anordnung durch die durch den Teilbarkeitsbegriff definierte partielle Ordnung.

Ist $d$ ein Ringelement, das sowohl Teiler von $a$ als auch Teiler von $b$ ist, dann heißt $d$ ein gemeinsamer Teiler von $a$ und $b$ . Gilt zusätzlich, dass jeder weitere gemeinsame Teiler von $a$ und $b$ auch ein Teiler von $d$ ist, dann heißt $d$ ein größter gemeinsamer Teiler von $a$ und $b$ .

Analog ist das $\operatorname{kgV}$ definiert: Ein Ringelement $v$ heißt kleinstes gemeinsames Vielfaches zweier Ringelemente $a$ und $b$ , wenn $v$ ein gemeinsames Vielfaches von $a$ und $b$ ist und seinerseits jedes andere gemeinsame Vielfache von $a$ und $b$ ein Vielfaches von $v$ ist.

Formal schreibt man diese Definition für einen Ring $R$ so:

$d = \operatorname{ggT}(a, b)\quad :\Longleftrightarrow\quad d \mid a,\; d \mid b,\; \forall e \in R: (e \mid a,\, e \mid b) \Rightarrow e \mid d$

$v = \operatorname{kgV}(a, b)\quad :\Longleftrightarrow\quad a \mid v,\; b \mid v,\; \forall e \in R: (a \mid e,\, b \mid e) \Rightarrow v \mid e$

Diese allgemeinere Definition lässt sich auf mehrere Zahlen ausweiten (sogar auf unendlich viele).

Beispiel: Im Gaußschen Zahlenring $\Z+\mathrm{i}\Z$ ist der größte gemeinsame Teiler von $2$ und $1 + 3 i$ gerade $1 + i$ , denn $2 = - i (1 + i) 2$ und $1 + 3 i = (1 + i)(2 + i)$ . Genau genommen ist $1 + i$ ein größter gemeinsamer Teiler, da alle zu dieser Zahl assoziierten Zahlen ebenfalls größte gemeinsame Teiler sind.

Nicht in jedem Ring existiert für zwei Elemente ein $\operatorname{ggT}$ oder ein $\operatorname{kgV}$ . Wenn sie einen $\operatorname{ggT}$ haben, können sie mehrere $\operatorname{ggT}$ ’s haben. Ist der Ring ein Integritätsring, dann sind alle $\operatorname{ggT}$ ’s zueinander assoziiert.

Ist $R$ ein Integritätsring, und haben die Elemente $a$ und $b$ ein $\operatorname{kgV}$ , dann haben sie auch einen $\operatorname{ggT}$ , und es gilt die Gleichung

$a \cdot b = \operatorname{ggT}(a, b) \cdot \operatorname{kgV}(a, b)$

Ist jedoch nur bekannt, dass ein $\operatorname{ggT}$ von $a$ und $b$ existiert, dann muss nicht unbedingt auch ein $\operatorname{kgV}$ existieren.

[Bearbeiten] Beispiel

Im Integritätsring $R = \mathbb{Z}[\sqrt{-3}]$ haben die Elemente

$a := 4 = 2\cdot 2 = (1 + \sqrt{-3})(1 - \sqrt{-3}),\quad b := (1 + \sqrt{-3})\cdot 2$

keinen $\operatorname{ggT}$ : Die Elemente $1 + \sqrt{-3}$ und $2$ sind zwei maximale gemeinsame Teiler (d. h. jeder gemeinsame Teiler, der von einem der beiden Elemente geteilt wird, ist zu diesem assoziiert), aber diese zwei Elemente sind nicht zueinander assoziiert, also gibt es keinen $\operatorname{ggT}$ von $a$ und $b$ .

Die genannten Elemente $1+\sqrt{-3}$ und $2$ haben aber ihrerseits einen $\operatorname{ggT}$ , nämlich $1$ . Dagegen haben sie kein $\operatorname{kgV}$ , denn wenn $v$ ein $\operatorname{kgV}$ wäre, dann folgt aus der „ $\operatorname{ggT}$ - $\operatorname{kgV}$ -Gleichung“, dass $v$ assoziiert zu $k:=(1 + \sqrt{-3})\cdot2$ sein muss. Das gemeinsame Vielfache $4$ ist jedoch kein Vielfaches von $k$ , also ist $k$ kein $\operatorname{kgV}$ und die beiden Elemente haben gar kein $\operatorname{kgV}$ .

Ein Integritätsring, in dem je zwei Elemente einen $\operatorname{ggT}$ besitzen, heißt $\operatorname{ggT}$ -Ring oder $\operatorname{ggT}$ -Bereich.

In einem $\operatorname{ggT}$ -Ring haben je zwei Elemente auch ein $\operatorname{kgV}$ .

In einem faktoriellen Ring haben je zwei Elemente einen $\operatorname{ggT}$ .

In einem euklidischen Ring lässt sich der $\operatorname{ggT}$ zweier Elemente mit dem Euklidischen Algorithmus bestimmen.

Von „http://de.wikipedia.org../../../g/r/%C3%B6/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler_und_kleinstes_gemeinsames_Vielfaches_b052.html“

Kategorie: Zahlentheorie