Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 27. Juni 2019 

KgV und ggT


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
In den natürlichen Zahlen N spielen der größte gemeinsame Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) eine wichtige Rolle.

Man sagt eine Zahl a teilt b (oder a ist Teiler von b geschrieben a | b ) wenn es eine Zahl c gibt so dass a·c = b ist. 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. Das kgV von a und b ist die kleinste natürliche Zahl v die sowohl von a als auch b geteilt wird.

Formell schreibt man:

  • t = ggT( a b ) <=> e | a und e | b dann gilt auch e | t
  • v = kgV( a b ) <=> a | f und b | f dann gilt auch v | f

Berechnung

ggT und kgV kann man über Primfaktorzerlegung (Faktorisierung) von a und b bestimmen. Ein Beispiel:

a = 63 = 3 2 *7
b = 105 = 3*5*7

Für den ggT nimmt man alle Primfaktoren die a und b gemeinsam haben - in dem Fall und 7 - und bildet daraus das Kommen Faktoren mit einem Exponenten vor wird jeweils der kleinste Exponent Das kgV wird ähnlich berechnet hier wird jeder Primfaktor mit jeweils dem höchsten Exponenten Für unser Beispiel also 3 2 5 und 7 das kgV ist

Die Faktorisierung großer Zahlen ist kein Problem. Eine einfachere Methode um den ggT berechnen hat der griechische Mathematiker Euklid bereits um 300 v. Chr. angegeben so genannte Euklidischen Algorithmus :

  1. setze m = a ; n = b
  2. berechne m : n mit Divisionsrest r
  3. setze m = n n = r
  4. ist n ≠ 0 fahre fort mit Schritt

Nach Ablauf erhält man m = ggT( a b ). Oftmals wird a b als Eingabe vorausgesetzt. Das ist bei Form des Euklidischen Algorithmus aber nicht notwendig sich hier die Zahlen von selbst vertauschen a < b sein sollte.

Durch den Zusammenhang

<math>kgV(a b) \cdot ggT(a b) = a\cdot

kann man nun aus dem ggT kgV berechnen.

Beispiele für die praktische Anwendung

kgV und ggT sind nützliche Hilfsmittel der Bruchrechnung. Zur Vereinfachung eines Bruchs berechnet man Zähler und Nenner durch ihren ggT:

<math>
\frac{72}{1080} =
 \frac{3 \cdot 24}{5 \cdot 9 \cdot = \frac{1}{15}  
</math>

Zur Addition von Brüchen muss man auf einen gemeinsamen Hauptnenner bringen. Der kleinste gemeinsame Nenner ist mit dem kgV identisch.

<math>
\frac{1}{10} + \frac{1}{12} =
 \frac{6}{60} + \frac{5}{60} = \frac{11}{60}  
</math>

kgV und ggT in weiteren algebraischen

kgV und ggT lassen sich nicht für natürliche (und ganze) Zahlen definieren. Man ihn z.B. auch für Polynome bilden. Statt der Primzahlzerlegung nimmt man die Zerlegung in Linearfaktoren:

f( x ) = x ² + 2 xy + 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 ).

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

Teilbarkeit ist ein Grundbegriff aus der Ringtheorie . Nicht in jedem Ring lässt sich ein kleinster gemeinsamer Teiler definieren. Gibt es für je zwei Ringelemente einen eindeutigen ggT sind auch kgV und Division mit Rest Solche Ringe heißen euklidisch da in ihnen Euklidische Algorithmus terminiert.




Bücher zum Thema KgV und ggT

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/KgV_und_ggT.html">KgV und ggT </a>