Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches

aus Wikipedia, der freien Enzyklopädie

Der größte gemeinsame Teiler (ggT oder gcd von engl. greatest common divisor) und das kleinste gemeinsame Vielfache (kgV oder lcm von engl. least common multiple) sind zwei zusammengehörende mathematische Begriffe. Sie spielen unter anderem in der Bruchrechnung und der Zahlentheorie eine Rolle.

Der größte gemeinsame Teiler zweier ganzer Zahlen $m$ und $n$ ist die größte natürliche Zahl, durch die sowohl $m$ als auch $n$ ohne Rest teilbar sind. Für $m = n = 0$ ist der größte gemeinsame Teiler nicht definiert; für die algebraische Definition gelten abweichende Eigenschaften.

Das kleinste gemeinsame Vielfache zweier ganzer Zahlen $m$ und $n$ ist die kleinste natürliche Zahl, die sowohl Vielfaches von $m$ als auch Vielfaches von $n$ ist.

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 Lemma von Bézout
5 Rechenregeln
6 kgV und ggT in weiteren algebraischen Strukturen
- 6.1 Beispiel
7 Weblinks

[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.

Die Berechnung des kleinsten gemeinsamen Vielfachen erfolgt, indem zuerst der größte gemeinsame Teiler berechnet wird. Daraus lässt sich dann das kleinste gemeinsame Vielfache berechenen:

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

Umgekehrt kann man mit dieser Formel auch den größten gemeinsamen Teiler aus dem kleinsten gemeinsamen Vielfachen berechnen.

[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] Lemma von Bézout

→ Hauptartikel: Lemma von Bézout

Nach dem Lemma von Bézout lässt sich der größte gemeinsame Teiler zweier ganzer Zahlen $m$ und $n$ als Linearkombination von $m$ und $n$ mit ganzzahligen Koeffizienten darstellen:

$\operatorname{ggT}(m,n) = s \cdot m + t \cdot n$ mit $s,t\in\mathbb{Z}$

Beispielsweise besitzt der größte gemeinsame Teiler von 12 und 18 die folgende Darstellung:

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

Die Koeffizienten $s$ und $t$ können mit dem erweiterten euklidischen Algorithmus berechnet werden.

[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$

Ist $a \equiv b\ (\bmod\ n)$ , so gilt:

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

Hält man eines der beiden Argumente der Funktion $\operatorname{ggT}$ fest, dann ist $\operatorname{ggT}$ eine multiplikative Funktion, denn für teilerfremde Zahlen $a$ und $b$ gilt

$\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.

[Bearbeiten] Weblinks

Online-Tool zur Berechnung des ggT und des kgV von zwei oder drei Zahlen
Verschiedene Online-Tools zur Primfaktorzerlegung, ggT und kgV.
Online-Tool zur Berechnung des ggT zweier Zahlen

Kategorie: Zahlentheorie

See also ebooksgratis.com: no banners, no cookies, totally FREE.