KgV und ggT

Stichpunkte

Allgemein
	wenn es eine Zahl c gibt
	In den natürlichen Zahlen N spielen der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) eine wichtige Rolle. Man sagt
	geschrieben a | b)
	so dass a·c = b ist
	eine Zahl a teilt b (oder a ist Teiler von b
	Umgekehrt heißt b dann auch ein Vielfaches von a
	Als ggT zweier Zahlen a und b bezeichnet man die größte natürliche Zahl t
	welche sowohl a als auch b teilt
	die sowohl von a als auch b geteilt wird
	Das kgV von a und b ist die kleinste natürliche Zahl v
	b) <=> a | f und b | f
	Formell schreibt man: t = ggT(a
	b) <=> e | a und e | b
	dann gilt auch v | f [Bearbeiten]
	dann gilt auch e | t v = kgV(a
Berechnung
	ggT und kgV kann man über die Primfaktorzerlegung (Faktorisierung) von a und b bestimmen
	3780) = 22 * 32 * 50 * 71 = 252 Für das kgV verwendet man die größten Exponenten der jeweiligen Basen: kgV(3528
	3780) = 23 * 33 * 51 * 72 = 52920 Die Faktorisierung großer Zahlen ist kein triviales Problem
	Ein Beispiel: a = 3528 = 23 * 32 * 50 * 72 b = 3780 = 22 *33 * 51 * 71 Für den ggT nimmt man die kleinsten Exponenten der zugehörigen Basen: ggT(3528
	Eine einfachere Methode
	um den ggT zu berechnen
	hat der griechische Mathematiker Euklid bereits um 300 v
	n = r ist n ≠ 0 fahre fort mit Schritt 2 Nach Ablauf erhält man m = ggT(a
	b)
	Chr. angegeben
	den so genannten Euklidischen Algorithmus: setze m = a; n = b berechne m:n mit Divisionsrest r setze m = n
	Oftmals wird a ≥ b als Eingabe vorausgesetzt
	Das ist bei dieser Form des Euklidischen Algorithmus aber nicht notwendig
	wenn a < b sein sollte
	da sich hier die Zahlen von selbst vertauschen
	b) = acdot b<math> kann man nun aus dem ggT das kgV berechnen. [Bearbeiten]
	b) cdot ggT(a
	Durch den Zusammenhang <math>kgV(a
kgV und ggT in weiteren algebraischen Strukturen
	kgV und ggT lassen sich nicht nur für natürliche (und ganze) Zahlen definieren
	Man kann ihn z.B. auch für Polynome bilden
	Statt der Primzahlzerlegung nimmt man hier die Zerlegung in Linearfaktoren: f(x) = x² + 2xy + y² = (x + y)² g(x) = x² - y² = (x + y) (x - y) Dann ist ggT(f
	g) = x + y und kgV(f
	g) = (x + y)² (x - y)
	da auch für Polynome eine Division mit Rest existiert. Teilbarkeit ist ein Grundbegriff aus der Ringtheorie
	Möglich wird dies
	Nicht in jedem Ring lässt sich jedoch ein kleinster gemeinsamer Teiler definieren
	so sind auch kgV und Division mit Rest eindeutig
	Gibt es jedoch für je zwei Ringelemente einen eindeutigen ggT
	da in ihnen der Euklidische Algorithmus terminiert.
	Solche Ringe heißen euklidisch

Dieser Artikel basiert auf dem Artikel KgV und ggT aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.