Nod und Nok von Zahlen sind der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache mehrerer Zahlen. Nicken und Nicken von drei oder mehr Zahlen Beispiele für die Definition von Nicken

Definition. Die größte natürliche Zahl, durch die die Zahlen a und b ohne Rest geteilt werden, heißt größter gemeinsamer Teiler (GCD) diese Nummern.

Finden wir den größten gemeinsamen Teiler der Zahlen 24 und 35.
Die Teiler von 24 sind die Zahlen 1, 2, 3, 4, 6, 8, 12, 24 und die Teiler von 35 sind die Zahlen 1, 5, 7, 35.
Wir sehen, dass die Zahlen 24 und 35 nur einen gemeinsamen Teiler haben – die Zahl 1. Solche Zahlen heißen gegenseitig prim.

Definition. Natürliche Zahlen werden aufgerufen gegenseitig prim, wenn ihr größter gemeinsamer Teiler (GCD) 1 ist.

Größter gemeinsamer Teiler (GCD) kann gefunden werden, ohne alle Teiler der gegebenen Zahlen aufzuschreiben.

Wenn wir die Zahlen 48 und 36 faktorisieren, erhalten wir:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Von den Faktoren, die in der Entwicklung der ersten dieser Zahlen enthalten sind, streichen wir diejenigen heraus, die nicht in der Entwicklung der zweiten Zahl enthalten sind (d. h. zwei Zweier).
Die verbleibenden Faktoren sind 2 * 2 * 3. Ihr Produkt ist gleich 12. Diese Zahl ist der größte gemeinsame Teiler der Zahlen 48 und 36. Es gibt auch den größten gemeinsamen Teiler von drei oder mehr Zahlen.

Finden größter gemeinsamer Teiler

2) Von den Faktoren, die in die Entwicklung einer dieser Zahlen einfließen, streichen Sie diejenigen durch, die nicht in die Entwicklung anderer Zahlen eingehen;
3) Finden Sie das Produkt der verbleibenden Faktoren.

Wenn alle gegebenen Zahlen durch eine davon teilbar sind, dann ist diese Zahl größter gemeinsamer Teiler gegebene Zahlen.
Beispielsweise ist der größte gemeinsame Teiler der Zahlen 15, 45, 75 und 180 die Zahl 15, da alle anderen Zahlen durch sie teilbar sind: 45, 75 und 180.

Kleinstes gemeinsames Vielfaches (LCM)

Definition. Kleinstes gemeinsames Vielfaches (LCM) Die natürlichen Zahlen a und b sind die kleinste natürliche Zahl, die ein Vielfaches von a und b ist. Das kleinste gemeinsame Vielfache (LCM) der Zahlen 75 und 60 kann ermittelt werden, ohne die Vielfachen dieser Zahlen hintereinander aufzuschreiben. Dazu zerlegen wir 75 und 60 in Primfaktoren: 75 = 3 * 5 * 5 und 60 = 2 * 2 * 3 * 5.
Schreiben wir die Faktoren auf, die in der Entwicklung der ersten dieser Zahlen enthalten sind, und fügen wir ihnen die fehlenden Faktoren 2 und 2 aus der Entwicklung der zweiten Zahl hinzu (d. h. wir kombinieren die Faktoren).
Wir erhalten fünf Faktoren 2 * 2 * 3 * 5 * 5, deren Produkt 300 ist. Diese Zahl ist das kleinste gemeinsame Vielfache der Zahlen 75 und 60.

Sie finden auch das kleinste gemeinsame Vielfache von drei oder mehr Zahlen.

Zu Finden Sie das kleinste gemeinsame Vielfache Um mehrere natürliche Zahlen zu erhalten, benötigen Sie:
1) faktorisiere sie in Primfaktoren;
2) Notieren Sie die Faktoren, die in die Entwicklung einer der Zahlen einfließen;
3) füge die fehlenden Faktoren aus den Erweiterungen der verbleibenden Zahlen hinzu;
4) Finden Sie das Produkt der resultierenden Faktoren.

Beachten Sie, dass, wenn eine dieser Zahlen durch alle anderen Zahlen teilbar ist, diese Zahl das kleinste gemeinsame Vielfache dieser Zahlen ist.
Beispielsweise ist das kleinste gemeinsame Vielfache der Zahlen 12, 15, 20 und 60 60, weil es durch alle diese Zahlen teilbar ist.

Pythagoras (VI. Jahrhundert v. Chr.) und seine Schüler untersuchten die Frage der Teilbarkeit von Zahlen. Sie nannten eine Zahl, die der Summe aller ihrer Teiler (ohne die Zahl selbst) entspricht, eine vollkommene Zahl. Beispielsweise sind die Zahlen 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) perfekt. Die nächsten vollkommenen Zahlen sind 496, 8128, 33.550.336. Die Pythagoräer kannten nur die ersten drei vollkommenen Zahlen. Der vierte – 8128 – wurde im 1. Jahrhundert bekannt. N. e. Der fünfte – 33.550.336 – wurde im 15. Jahrhundert gefunden. Bis 1983 waren bereits 27 perfekte Zahlen bekannt. Aber Wissenschaftler wissen immer noch nicht, ob es ungerade vollkommene Zahlen gibt oder ob es eine größte vollkommene Zahl gibt.
Das Interesse der antiken Mathematiker an Primzahlen beruht auf der Tatsache, dass jede Zahl entweder eine Primzahl ist oder als Produkt von Primzahlen dargestellt werden kann, d. h. Primzahlen sind wie Bausteine, aus denen die übrigen natürlichen Zahlen aufgebaut sind.
Sie haben wahrscheinlich bemerkt, dass Primzahlen in der Reihe der natürlichen Zahlen ungleichmäßig vorkommen – in einigen Teilen der Reihe gibt es mehr davon, in anderen weniger. Aber je weiter wir uns in der Zahlenreihe bewegen, desto seltener werden Primzahlen. Es stellt sich die Frage: Gibt es eine letzte (größte) Primzahl? Der antike griechische Mathematiker Euklid (3. Jahrhundert v. Chr.) bewies in seinem Buch „Elemente“, das zweitausend Jahre lang das wichtigste Lehrbuch der Mathematik war, dass es unendlich viele Primzahlen gibt, d. h. hinter jeder Primzahl steht eine noch größere Primzahl Nummer.
Um Primzahlen zu finden, entwickelte ein anderer griechischer Mathematiker der gleichen Zeit, Eratosthenes, diese Methode. Er schrieb alle Zahlen von 1 bis zu einer Zahl auf und strich dann eine durch, die weder eine Primzahl noch eine zusammengesetzte Zahl ist, und strich dann durch eins alle Zahlen durch, die nach 2 kamen (Zahlen, die ein Vielfaches von 2 sind, also 4). 6, 8 usw.). Die erste verbleibende Zahl nach 2 war 3. Dann wurden nach zwei alle Zahlen nach 3 (Zahlen, die ein Vielfaches von 3 waren, also 6, 9, 12 usw.) durchgestrichen. letztlich blieben nur die Primzahlen ungekreuzt.

Um den GCD (größten gemeinsamen Teiler) zweier Zahlen zu ermitteln, müssen Sie Folgendes tun:

2. Finden (unterstreichen) Sie alle gemeinsamen Primfaktoren in den resultierenden Erweiterungen.

3. Finden Sie das Produkt gemeinsamer Primfaktoren.

Um das LCM (kleinstes gemeinsames Vielfaches) zweier Zahlen zu ermitteln, benötigen Sie:

1. Teilen Sie die angegebenen Zahlen in Primfaktoren.

2. Die Entwicklung einer von ihnen wird durch diejenigen Faktoren der Entwicklung der anderen Zahl ergänzt, die nicht in der Entwicklung der ersten Zahl enthalten sind.

3. Berechnen Sie das Produkt der resultierenden Faktoren.

gcd finden

GCD ist der größte gemeinsame Teiler.

Um den größten gemeinsamen Teiler mehrerer Zahlen zu finden, benötigen Sie:

• Bestimmen Sie die gemeinsamen Faktoren beider Zahlen.
• Finden Sie das Produkt gemeinsamer Faktoren.

Ein Beispiel für die Suche nach GCD:

Lassen Sie uns den gcd der Nummern 315 und 245 ermitteln.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Schreiben wir die gemeinsamen Faktoren beider Zahlen auf:

3. Finden Sie das Produkt gemeinsamer Faktoren:

GCD(315, 245) = 5 * 7 = 35.

Antwort: GCD(315, 245) = 35.

Das NOC finden

LCM ist das kleinste gemeinsame Vielfache.

Um das kleinste gemeinsame Vielfache mehrerer Zahlen zu finden, benötigen Sie:

• Faktorisieren Sie Zahlen in Primfaktoren;
• Schreiben Sie die Faktoren auf, die bei der Entwicklung einer der Zahlen berücksichtigt werden.
• Fügen wir ihnen die fehlenden Faktoren aus der Entwicklung der zweiten Zahl hinzu;
• Finden Sie das Produkt der resultierenden Faktoren.

Ein Beispiel für die Suche nach dem LOC:

Finden wir das LCM der Zahlen 236 und 328:

1. Zerlegen wir die Zahlen in Primfaktoren:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Schreiben wir die Faktoren auf, die in der Entwicklung einer der Zahlen enthalten sind, und fügen wir ihnen die fehlenden Faktoren aus der Entwicklung der zweiten Zahl hinzu:

2; 2; 59; 2; 41.

3. Finden Sie das Produkt der resultierenden Faktoren:

LOC(236, 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Antwort: LCM(236, 328) = 19352.

Der größte gemeinsame Faktor ist eine weitere Metrik, die die Arbeit mit Brüchen erleichtert. Sehr oft ergeben Berechnungen Brüche mit sehr großen Zähler- und Nennerwerten. Es ist möglich, solche Zahlen Schritt für Schritt zu reduzieren, aber das ist extrem zeitaufwändig, sodass es einfacher ist, sofort einen GCD zu finden und ihn entsprechend zu reduzieren. Schauen wir uns das Thema genauer an.

Was ist GCD?

Der größte gemeinsame Teiler (GCD) einer Zahlenreihe ist die größte Zahl, durch die jede Zahl in der Reihe ohne Rest geteilt werden kann.

Wie finde ich GCD?

Um den gcd zu finden, ist es notwendig, jede der Zahlen in Primfaktoren zu zerlegen und den gemeinsamen Teil zu isolieren.

Sie haben sich dafür keine spezielle Formel ausgedacht, aber es gibt einen Berechnungsalgorithmus.

Lassen Sie uns ein Beispiel für die Ermittlung des größten gemeinsamen Teilers zweier natürlicher Zahlen geben: 540 und 252. Lassen Sie uns 640 in Primfaktoren faktorisieren. Die Reihenfolge der Aktionen ist wie folgt:

• Teilen Sie die Zahl durch die kleinstmögliche Primzahl. Das heißt, wenn eine Zahl durch 2, 3 oder 5 teilbar ist, müssen Sie zuerst durch 5 teilen. Nur um nicht verwirrt zu werden.
• Das resultierende Ergebnis dividieren wir durch die kleinstmögliche Primzahl.
• Wir wiederholen die Division jedes erhaltenen Ergebnisses, bis wir eine Primzahl erhalten.

Lassen Sie uns nun das gleiche Verfahren in der Praxis durchführen.

• 540: 2=270
• 270:2=135
• 135: 3 =45
• 45: 3=15
• 15: 5 = 3

Schreiben wir das Ergebnis als Gleichheit 540=2*2*3*3*3*5. Um das Ergebnis aufzuschreiben, müssen Sie die letzte resultierende Zahl mit allen Teilern multiplizieren.

Machen wir dasselbe mit der Zahl 252:

• 252: 2=126
• 126: 2=63
• 63: 3=21
• 21: 3 = 7

Schreiben wir das Ergebnis auf: 252=2*2*3*3*7.

Jede Erweiterung hat die gleichen Nummern. Finden wir sie, das sind zwei Zahlen 2 und zwei Zahlen 3. Nur 7 und 3*5 unterscheiden sich.

Um den GCD zu ermitteln, müssen Sie die gemeinsamen Faktoren multiplizieren. Das heißt, es wird zwei Zweier und zwei Dreier in der Arbeit geben.

GCD=2*2*3*3=36

Wie können Sie das nutzen?

Aufgabe: Reduziere den Bruch $$252\over540$$.

Den gcd für diese beiden Zahlen haben wir bereits gefunden, jetzt verwenden wir einfach den bereits berechneten Wert.

Reduzieren Sie Zähler und Nenner des Bruchs um 36 und erhalten Sie die Antwort.

$$(252\over540) =(7\over15)$$ – um schnell zu reduzieren, schauen Sie sich einfach die Zerlegung von Zahlen an.

Wenn 540=2*2*3*3*3*5 und GCD=36=2*2*3*3, dann ist 540 = 36*3*5. Und wenn wir 540 durch 36 dividieren, erhalten wir 3*5=15.

Ohne GCD müssten wir Abkürzungen in einer langen Zeile schreiben. Darüber hinaus gibt es Zeiten, in denen nicht klar ist, ob ein Bruch überhaupt gekürzt werden kann. Für solche Situationen hat die Mathematik die Zerlegung von Zahlen in Primfaktoren und gcd erfunden.

Was haben wir gelernt?

Wir haben gelernt, was der größte gemeinsame Teiler eines Zahlenpaares ist, haben herausgefunden, wie man den Exponenten in der Praxis verwendet, haben das Problem gelöst, GCD zu finden und GCD zum Reduzieren von Brüchen zu verwenden. Wir haben festgestellt, dass Sie mit GCD umständliche Brüche einfacher und schneller reduzieren können, indem Sie den GCD für Zähler und Nenner ermitteln.

Test zum Thema

Artikelbewertung

Durchschnittliche Bewertung: 4.3. Insgesamt erhaltene Bewertungen: 204.

Eine der Aufgaben, die für moderne Schulkinder, die es gewohnt sind, in Gadgets eingebaute Taschenrechner angemessen und unangemessen zu verwenden, ein Problem darstellt, besteht darin, den größten gemeinsamen Teiler (GCD) von zwei oder mehr Zahlen zu finden.

Es ist unmöglich, ein mathematisches Problem zu lösen, wenn man nicht weiß, worum es eigentlich geht. Dazu müssen Sie wissen, was dieser oder jener Ausdruck bedeutet., in der Mathematik verwendet.

Allgemeine Konzepte und Definitionen

Wissenswertes:

1. Wenn eine bestimmte Zahl verwendet werden kann, um verschiedene Objekte zu zählen, zum Beispiel neun Säulen, sechzehn Häuser, dann ist das natürlich. Der kleinste von ihnen wird einer sein.
2. Wenn eine natürliche Zahl durch eine andere natürliche Zahl geteilt wird, wird die kleinere Zahl als Teiler der größeren Zahl bezeichnet.
3. Wenn zwei oder mehr verschiedene Zahlen durch eine bestimmte Zahl ohne Rest teilbar sind, dann sagt man, dass letzterer ihr gemeinsamer Teiler (CD) ist.
4. Der größte der ODs wird als größter gemeinsamer Teiler (GCD) bezeichnet.
5. Wenn eine Zahl in diesem Fall nur zwei natürliche Teiler hat (sich selbst und einen), wird sie Primzahl genannt. Die kleinste unter ihnen ist zwei, und es ist auch die einzige gerade Zahl in ihrer Reihe.
6. Wenn zwei Zahlen einen maximalen gemeinsamen Teiler von eins haben, dann sind sie relativ prim.
7. Eine Zahl, die mehr als zwei Teiler hat, heißt zusammengesetzt.
8. Der Prozess, alle Primfaktoren zu finden, die, wenn sie miteinander multipliziert werden, dem Produkt den Anfangswert ergeben, wird in der Mathematik als Zerlegung in Primfaktoren bezeichnet. Darüber hinaus können identische Faktoren in der Erweiterung mehrfach vorkommen.

In der Mathematik werden folgende Notationen akzeptiert:

1. Teiler D (45) = (1;3;5;9;45).
2. OD (8;18) = (1;2).
3. GCD (8;18) = 2.

Verschiedene Möglichkeiten, GCD zu finden

Der einfachste Weg, die Frage zu beantworten, ist So finden Sie GCD für den Fall, dass die kleinere Zahl ein Teiler der größeren ist. In einem solchen Fall handelt es sich um den größten gemeinsamen Teiler.

Beispiel: GCD (15;45) = 15, GCD (48;24) = 24.

Solche Fälle in der Mathematik sind jedoch sehr selten. Um GCD zu finden, werden daher komplexere Techniken verwendet, obwohl es dennoch dringend empfohlen wird, diese Option vor Beginn der Arbeit zu überprüfen.

Methode der Zerlegung in einfache Faktoren

Wenn Sie den gcd von zwei oder mehr verschiedenen Zahlen ermitteln müssen, es reicht aus, jeden von ihnen in einfache Faktoren zu zerlegen und dann den Prozess der Multiplikation derjenigen durchzuführen, die in jeder der Zahlen vorhanden sind.

Beispiel 1

Schauen wir uns an, wie man GCD 36 und 90 findet:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

GCD (36;90) = 1*2*3*3 = 18.

Nun wollen wir sehen, wie wir das Gleiche finden bei drei Zahlen Nehmen wir als Beispiel 54; 162; 42.

Wir wissen bereits, wie man 36 zerlegt. Lassen Sie uns den Rest herausfinden:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Somit ist gcd (36;162;42) = 1*2*3 = 6.

Es ist zu beachten, dass das Schreiben einer Einheit in die Erweiterung völlig optional ist.

Betrachten wir einen Weg wie man Primfaktoren einfach berücksichtigt Dazu schreiben wir links die benötigte Zahl und rechts einfache Teiler.

Spalten können entweder durch ein Trennzeichen oder eine einfache vertikale Linie getrennt werden.

1. 36 / 2 Wir werden unseren Teilungsprozess fortsetzen;
2. 18/2 weiter;
3. 9/3 und noch einmal;
4. 3/3 ist jetzt ziemlich elementar;
5. 1 - das Ergebnis ist fertig.

Erforderlich 36 = 2*2*3*3.

Euklidischer Weg

Diese Option ist der Menschheit seit der Zeit der antiken griechischen Zivilisation bekannt, sie ist in vielerlei Hinsicht einfacher und wird dem großen Mathematiker Euklid zugeschrieben, obwohl früher sehr ähnliche Algorithmen verwendet wurden. Diese Methode besteht darin, den folgenden Algorithmus zu verwenden, wir dividieren die größere Zahl mit einem Rest durch die kleinere. Dann dividieren wir unseren Divisor durch den Rest und machen so im Kreis weiter, bis eine vollständige Division erfolgt. Der letzte Wert wird sich als der gewünschte größte gemeinsame Teiler herausstellen.

Lassen Sie uns ein Beispiel für die Verwendung dieses Algorithmus geben:

Versuchen wir herauszufinden, welchen GCD die 816 und 252 haben:

1. 816 / 252 = 3 und der Rest ist 60. Jetzt dividieren wir 252 durch 60;
2. 252 / 60 = 4, der Rest beträgt dieses Mal 12. Setzen wir unseren Kreisprozess fort und dividieren sechzig durch zwölf;
3. 60 / 12 = 5. Da wir dieses Mal keinen Rest erhalten haben, haben wir ein fertiges Ergebnis, zwölf wird der gesuchte Wert sein.

Also, am Ende unseres Prozesses wir haben gcd (816;252) = 12.

Aktionen, wenn es notwendig ist, den GCD zu ermitteln, wenn mehr als zwei Werte angegeben werden

Wir haben bereits herausgefunden, was zu tun ist, wenn es zwei verschiedene Zahlen gibt. Jetzt erfahren wir, wie wir uns verhalten, wenn es welche gibt 3 oder mehr.

Bei aller scheinbaren Komplexität wird uns diese Aufgabe keine Probleme mehr bereiten. Nun wählen wir zwei beliebige Zahlen aus und ermitteln den gesuchten Wert. Der nächste Schritt besteht darin, den gcd des erhaltenen Ergebnisses und das Drittel der angegebenen Werte zu ermitteln. Dann handeln wir wieder nach dem uns bereits bekannten Prinzip für das vierte Fünftel und so weiter.

Abschluss

Trotz der scheinbar großen Komplexität der uns zunächst gestellten Aufgabe ist in Wirklichkeit alles einfach, Die Hauptsache ist, den Teilungsprozess genau durchführen zu können und befolgen Sie einen der beiden oben beschriebenen Algorithmen.

Obwohl beide Methoden in einer weiterführenden Schule durchaus akzeptabel sind Die erste Methode wird viel häufiger verwendet. Dies liegt daran, dass beim Studium des nächsten Bildungsthemas – der Bestimmung des größten gemeinsamen Vielfachen (LCM) – eine Faktorisierung erforderlich sein wird. Es ist jedoch noch einmal erwähnenswert, dass die Verwendung des Euklidischen Algorithmus in keiner Weise als fehlerhaft angesehen werden kann.

Video

In diesem Video erfahren Sie, wie Sie den größten gemeinsamen Teiler ermitteln.

Betrachten wir zwei Hauptmethoden zur Ermittlung der GCD auf zwei Arten: mithilfe des euklidischen Algorithmus und durch Zerlegung in Primfaktoren. Wenden wir beide Methoden auf zwei, drei oder mehr Zahlen an.

Euklidischer Algorithmus zum Finden von GCD

Der euklidische Algorithmus erleichtert die Berechnung des größten gemeinsamen Faktors zweier positiver Zahlen. Die Formulierungen und Beweise des Euklid-Algorithmus haben wir im Abschnitt „Größter gemeinsamer Teiler: Determinante, Beispiele“ vorgestellt.

Der Kern des Algorithmus besteht darin, nacheinander eine Division mit einem Rest durchzuführen, bei der eine Reihe von Gleichheiten der Form erhalten werden:

a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Wir können die Teilung beenden, wenn r k + 1 = 0, dabei r k = gcd (a , b).

Beispiel 1

64 Und 48 .

Lösung

Führen wir die folgenden Notationen ein: a = 64, b = 48.

Basierend auf dem Euklidischen Algorithmus führen wir eine Division durch 64 An 48 .

Wir erhalten 1 und den Rest 16. Es stellt sich heraus, dass q 1 = 1, r 1 = 16.

Der zweite Schritt ist die Aufteilung 48 bei 16 erhalten wir 3. Also q 2 = 3, A r 2 = 0 . Somit ist die Zahl 16 der größte gemeinsame Teiler der Zahlen aus der Bedingung.

Antwort: GCD (64, 48) = 16.

Beispiel 2

Was ist der GCD der Zahlen? 111 Und 432 ?

Lösung

Wir teilen 432 An 111 . Nach dem euklidischen Algorithmus erhalten wir die Gleichungskette 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.

Somit ist der größte gemeinsame Teiler von Zahlen 111 Und 432 – das ist 3.

Antwort: GCD (111, 432) = 3.

Beispiel 3

Finden Sie den größten gemeinsamen Teiler der Zahlen 661 und 113.

Lösung

Teilen wir die Zahlen der Reihe nach und erhalten wir GCD (661 , 113) = 1 . Das bedeutet, dass 661 und 113 relativ Primzahlen sind. Wir könnten dies herausfinden, bevor wir mit der Berechnung beginnen, wenn wir eine Tabelle mit Primzahlen konsultieren.

Antwort: GCD (661, 113) = 1.

Ermitteln des GCD durch Faktorisieren von Zahlen in Primfaktoren

Um mit der Faktorisierungsmethode den größten gemeinsamen Teiler zweier Zahlen zu finden, ist es notwendig, alle Primfaktoren zu multiplizieren, die man durch Faktorisieren dieser beiden Zahlen erhält und denen sie gemeinsam sind.

Beispiel 4

Wenn wir die Zahlen 220 und 600 in Primfaktoren zerlegen, erhalten wir zwei Produkte: 220 = 2 2 5 11 Und 600 = 2 2 2 3 5 5. Die gemeinsamen Faktoren dieser beiden Produkte sind 2, 2 und 5. Das bedeutet, dass GCD (220, 600) = 2 2 5 = 20.

Beispiel 5

Finden Sie den größten gemeinsamen Teiler von Zahlen 72 Und 96 .

Lösung

Finden Sie alle Primfaktoren von Zahlen 72 Und 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Die gemeinsamen Primfaktoren für zwei Zahlen sind 2, 2, 2 und 3. Das bedeutet, dass GCD (72, 96) = 2 2 2 3 = 24.

Antwort: GCD (72, 96) = 24.

Die Regel zum Ermitteln des größten gemeinsamen Teilers zweier Zahlen basiert auf den Eigenschaften des größten gemeinsamen Teilers, nach der ggT (m a 1, m b 1) = m ggT (a 1, b 1), wobei m eine beliebige positive ganze Zahl ist .

Ermitteln des gcd von drei oder mehr Zahlen

Unabhängig von der Anzahl der Zahlen, für die wir den GCD ermitteln müssen, folgen wir demselben Algorithmus, der darin besteht, nacheinander den GCD von zwei Zahlen zu ermitteln. Dieser Algorithmus basiert auf der Anwendung des folgenden Satzes: GCD mehrerer Zahlen a 1 , a 2 , … , a k gleich der Zahl dk, die durch sequentielle Berechnung des gcd ermittelt wird (a 1 , a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .

Beispiel 6

Finden Sie den größten gemeinsamen Teiler der vier Zahlen 78, 294, 570 und 36 .

Lösung

Führen wir die Notation ein: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Beginnen wir damit, den gcd der Nummern 78 und 294 zu ermitteln: d 2 = GCD (78 , 294) = 6 .

Beginnen wir nun damit, d 3 = GCD (d 2 , a 3) = GCD (6, 570) zu finden. Nach dem Euklid-Algorithmus 570 = 6 95. Das bedeutet es d 3 = GCD (6 , 570) = 6 .

Finden wir d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 ohne Rest durch 6 teilbar. Dadurch können wir bekommen d 4 = GCD (6 , 36) = 6 .

d4 = 6, das heißt GCD (78 , 294 , 570 , 36) = 6 .

Antwort:

Schauen wir uns nun eine andere Möglichkeit zur Berechnung des GCD für diese und weitere Zahlen an. Wir können den ggT ermitteln, indem wir alle gängigen Primfaktoren von Zahlen multiplizieren.

Beispiel 7

Berechnen Sie den GCD der Zahlen 78, 294, 570 und 36 .

Lösung

Zerlegen wir diese Zahlen in Primfaktoren: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.

Für alle vier Zahlen sind die gemeinsamen Primfaktoren die Zahlen 2 und 3.

Es stellt sich heraus, dass GCD (78, 294, 570, 36) = 2 3 = 6.

Antwort: GCD (78, 294, 570, 36) = 6.

GCD negativer Zahlen finden

Wenn wir es mit negativen Zahlen zu tun haben, können wir die Moduli dieser Zahlen verwenden, um den größten gemeinsamen Teiler zu finden. Wir können dies tun, indem wir die Eigenschaft von Zahlen mit entgegengesetzten Vorzeichen kennen: Zahlen N Und -N haben die gleichen Teiler.

Beispiel 8

Finden Sie den ggT negativer Ganzzahlen − 231 Und − 140 .

Lösung

Um Berechnungen durchzuführen, nehmen wir die Module der in der Bedingung angegebenen Zahlen. Dies werden die Nummern 231 und 140 sein. Schreiben wir es kurz auf: GCD (− 231 , − 140) = GCD (231, 140) . Jetzt wenden wir den euklidischen Algorithmus an, um Primfaktoren zweier Zahlen zu finden: 231 = 140 · 1 + 91 ; 140 = 91 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 1 + 7 und 42 = 7 6. Wir erhalten, dass GCD (231, 140) = 7 .

Und seit GCD (− 231 , − 140) = GCD (231 , 140) , dann gcd der Zahlen − 231 Und − 140 gleicht 7 .

Antwort: GCD (− 231, − 140) = 7.

Beispiel 9

Bestimmen Sie den ggT von drei Zahlen − 585, 81 und − 189 .

Lösung

Ersetzen wir die negativen Zahlen in der obigen Liste durch ihre absoluten Werte, erhalten wir GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Dann zerlegen wir alle diese Zahlen in Primfaktoren: 585 = 3 3 5 13, 81 = 3 3 3 3 und 189 = 3 3 3 7. Den drei Zahlen gemeinsam sind die Primfaktoren 3 und 3. Es stellt sich heraus, dass GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.

Antwort: GCD (− 585, 81, − 189) = 9.

Wenn Sie einen Fehler im Text bemerken, markieren Sie ihn bitte und drücken Sie Strg+Eingabetaste