Der größte gemeinsame Teiler (GCF) ist die größte Zahl, durch die zwei oder mehr Zahlen geteilt werden können. Dies ohne Rückstände zu hinterlassen.
Das heißt, der größte gemeinsame Teiler oder GCF ist die höchste Zahl, durch die eine Menge von Zahlen geteilt werden kann, was eine ganze Zahl ergibt.
Ein Teiler kann formal als die Zahl definiert werden, die in einem anderen genau n-mal enthalten ist.
Es sollte beachtet werden, dass die Zahlen, auf denen der GCF berechnet wird, ungleich Null sein müssen.
Um es besser zu erklären, schauen wir uns ein Beispiel an. Angenommen, wir haben 35 und 15. Somit beobachten wir, was die Teiler von jedem sind:
- Teiler von 35 → 35,7,5,1
- Teiler von 15 → 15,5,3,1
Daher ist der größte gemeinsame Faktor von 35 und 15 5.
Es ist erwähnenswert, dass, wenn die gemeinsamen Teiler zweier Zahlen nur 1 und -1 sind, sie "primer zueinander" genannt werden.
Methoden zur Berechnung des größten gemeinsamen Teilers
Wir können die folgenden drei Methoden unterscheiden, um den größten gemeinsamen Teiler zu berechnen:
- Primfaktorzerlegung: Die Zahlen werden in Primzahlen zerlegt. Um dann den GCF zu berechnen, nehmen wir die gewöhnlichen Zahlen mit der niedrigsten Potenz. Angenommen, wir haben 216 und 156:
216/2=108
108/2=54
54/2=27
27/3=9
9/3=3
3/3=1
216=(3^3)*(2^3)
156/2=78
78/2=39
39/3=13
13/13=1
156=13*3*(2^2)
Daher wäre der größte gemeinsame Teiler zwischen beiden Zahlen: (2 2) * 3 = 12
Nehmen wir nun an, wir haben drei Elemente: 315, 441 und 819
315= (3^2)*7*5
441= (3^2)*(7^2)
819= (3^2)*7*13
Dann, nach ihrer Aufgliederung, indem jeder Teiler mit seiner niedrigsten Potenz genommen wird, wäre das Ergebnis:
GCF = (3 2) * 7 = 63
- Euklids Algorithmus: Beim Teilen zu Komm herein b, erhält man einen Quotienten c und ein r. Also der größte gemeinsame Teiler von zu Ja b ist das gleiche wie b Ja r. Dies unter Berücksichtigung folgender Punkte: a = bc + r. Um es besser zu verstehen, wenden wir diese Methode auf das zuvor gezeigte Beispiel mit 216 und 156 an.
216/156 = 1 mit Rest von 60
jetzt teilen wir 156/60 = 2 mit Rest 36
Wir teilen wieder 60/36 = 1 mit Rest 24
Wir teilen wieder 36/24 = 1 mit Rest 12
Und schließlich dividieren wir 24/12 = 2 mit Rest 0
Daher ist der größte gemeinsame Teiler 12. Wie wir sehen, müssen wir teilen, bis der Rest 0 ist und der letzte Teiler der GCF ist.
- Basierend auf dem kleinsten gemeinsamen Vielfachen: Die Zahlen werden multipliziert und das Ergebnis durch ihr kleinstes gemeinsames Vielfaches (LCM) dividiert.
Wir müssen uns daran erinnern, dass das kleinste gemeinsame Vielfache (LCM) die kleinste Zahl ist, die die Bedingung erfüllt, ein Vielfaches aller Elemente einer Menge von Zahlen zu sein.
Das heißt, zurück zum gleichen Beispiel können wir wie folgt zerlegen:
216 = (3 3) * (2 3) und 156 = 13 * 3 * (2 2) 204 = 3 * (2 2) * 17 168 = 3 * (2 3) * 7
Das kleinste gemeinsame Vielfache wäre: (3 3) * (2 3) * 13 * 17 * 7 = 334.152
Also: GCD = 216 * 156 / 2,808 = 12
Es ist erwähnenswert, dass diese Methode nur für zwei Zahlen funktioniert.