MatheAss 9.0Algebra

ggT und kgV

Zu zwei oder mehr positiven ganzen Zahlen werden der größte gemeinsame Teiler, das kleinste gemeinsame Vielfache und ihre Teilermengen bestimmt.

Der ggT ist das größte Element in der Schnittmenge der Teilermengen von a und b. In der Bruchrechnung ist der ggT von Zähler und Nenner die größte Zahl, mit der der Bruch gekürzt werden kann.

Das kgV ist das kleinste Element in der Schnittmenge der Vielfachenmengen von a und b. In der Bruchrechnung bezeichnet man das kgV zweier Nenner als den Hauptnenner.

Hat man den ggT(a,b) bereits bestimmt, so erhält man das kgV(a,b) nach der Formel

kgV(a,b) = a·b / ggT(a,b)

Beispiel 1:

a = 24
b = 256

größter gemeinsamer Teiler              ggT = 8
kleinstes gemeinsames Vielfaches   kgV = 768

Teilermengen:
T(a) = { 1 2 3 4 6 8 12 24}
T(b) = { 1 2 4 8 16 32 64 128 256}

T(a) ∩ T(b) = { 1 2 4 8}

Beispiel 2:

a = 195
b = 234
c = 273

größter gemeinsamer Teiler              ggT = 39
kleinstes gemeinsames Vielfaches   kgV = 8190

Teilermengen: 
T(a) = { 1 3 5 13 15 39 65 195}
T(b) = { 1 2 3 6 9 13 18 26 39 78 117 234}
T(c) = { 1 3 7 13 21 39 91 273}

T(a) ∩ T(b) ∩ T(c) = { 1 3 13 39}

Beispiel 3:

Zusätzlich werden die Summe aller Teiler σ(n) und die Summe der echten Teiler σ*(n) bestimmt.
Zahlen, die gleich der Summe ihrer echten Teiler sind, nennt man vollkommene Zahlen.

a = 6
b = 28
c = 496
d = 8128
e = 33550336
f  = 8589869056
g = 137438691328

Größter gemeinsamer Teiler                  ggT = 2
Kleinstes gemeinsames Vielfaches       kgV = 1,21993659586792E25

Teilermengen : 
T(a) = { 1 2 3 6 }
T(b) = { 1 2 4 7 14 28 }
T(c) = { 1 2 4 8 16 31 62 124 248 496 }
T(d) = { 1 2 4 8 16 32 64 127 254 508 1016 2032 4064 8128 }
T(e) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16382 32764 65528 131056 262112 524224 ... }
T(f) =  { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131071 262142 524284 ... }
T(g) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524287 ... }

T(a) ∩ T(b) ∩ T(c) ∩ T(d) ∩ T(e) ∩ T(f) ∩ T(g) = { 1 2 }

Teilersummen : 
σ(a) = 12                     σ*(a) = 6                           vollkommene Zahl
σ(b) = 56                     σ*(b) = 28                         vollkommene Zahl
σ(c) = 992                   σ*(c) = 496                       vollkommene Zahl
σ(d) = 16256               σ*(d) = 8128                     vollkommene Zahl
σ(e) = 67100672         σ*(e) = 33550336             vollkommene Zahl
σ(f) =  17179738112    σ*(f) = 8589869056          vollkommene Zahl
σ(g) = 274877382656  σ*(g) = 137438691328     vollkommene Zahl

Die erste Hälfte der Teilermenge bildet offenbar jedesmal die Folge der Potenzen von 2.
(Siehe auch Primfaktorzerlegung)

Verfahren

Der größte gemeinsame Teiler zweier Zahlen kann aus ihren Primfaktorzerlegungen ermittelt werden. Ist bei großen Zahlen aber die Primfaktorzerlegung nur schwer zu ermitteln, hilft der nach Euklid benannte Algorithmus weiter.

Euklid nutzte aus, dass sich der ggT zweier Zahlen nicht ändert, wenn man die kleinere von der größeren abzieht. Heute verwendet man statt dem Subtraktionsalgorithmus meist den schnelleren Divisionsalgorithmus, bei dem die Differenz der Zahlen durch den Rest bei der Division ersetzt wird.

Divisionsalgorithmus in PASCAL:

function ggT(a,b:integer):integer;
  var 
    r: integer;		
  begin 
    repeat
      r := a mod b;
      a := b;
      b := r;
    until r=0;
    result := a;
  end;

www.matheass.eu