Aber viele natürliche Zahlen sind durch andere natürliche Zahlen ohne Rest teilbar.

zum Beispiel:

Die Zahl 12 ist teilbar durch 1, durch 2, durch 3, durch 4, durch 6, durch 12;

Die Zahl 36 ist teilbar durch 1, durch 2, durch 3, durch 4, durch 6, durch 12, durch 18, durch 36.

Die Zahlen, durch die die Zahl teilbar ist (bei 12 sind es 1, 2, 3, 4, 6 und 12), werden aufgerufen Zahlenteiler. Teiler einer natürlichen Zahl a ist die natürliche Zahl, die die gegebene Zahl teilt a ohne jede Spur. Eine natürliche Zahl, die mehr als zwei Teiler hat, wird aufgerufen zusammengesetzt. Beachten Sie, dass die Zahlen 12 und 36 gemeinsame Teiler haben. Dies sind die Zahlen: 1, 2, 3, 4, 6, 12. Der größte Teiler dieser Zahlen ist 12.

Gemeinsamer Teiler zweier gegebener Zahlen a und b ist die Zahl, durch die beide gegebenen Zahlen ohne Rest teilbar sind a und b. Gemeinsamer Teiler mehrerer Zahlen (ggT) ist die Zahl, die als Teiler für jeden von ihnen dient.

Kurz gesagt der größte gemeinsame Teiler von Zahlen a und b werden so geschrieben:

Beispiel: ggT (12; 36) = 12.

Die Teiler von Zahlen im Lösungsdatensatz werden durch einen Großbuchstaben „D“ gekennzeichnet.

Beispiel:

ggT (7; 9) = 1

Die Zahlen 7 und 9 haben nur einen gemeinsamen Teiler - die Zahl 1. Solche Zahlen werden genannt teilerfremdChi-Slam.

Koprime-Zahlen sind natürliche Zahlen, die nur einen gemeinsamen Teiler haben - die Zahl 1. Ihr ggT ist 1.

Größter gemeinsamer Teiler (ggT), Eigenschaften.

• Haupteigenschaft: größter gemeinsamer Teiler m und n durch jeden gemeinsamen Teiler dieser Zahlen teilbar ist. Beispiel: für die Zahlen 12 und 18 ist der größte gemeinsame Teiler 6; sie ist durch alle gemeinsamen Teiler dieser Zahlen teilbar: 1, 2, 3, 6.
• Korollar 1: Menge gemeinsamer Teiler m und n fällt mit der Menge der Teiler ggT( m, n).
• Korollar 2: Menge gemeinsamer Vielfacher m und n stimmt mit der Menge mehrerer LCMs überein ( m, n).

Das bedeutet insbesondere, dass man, um einen Bruch auf eine irreduzible Form zu bringen, Zähler und Nenner durch ihren ggT dividieren muss.

• Größter gemeinsamer Teiler von Zahlen m und n kann als das kleinste positive Element der Menge aller ihrer Linearkombinationen definiert werden:

und daher als Linearkombination von Zahlen darstellen m und n:

Dieses Verhältnis heißt Bezouts Verhältnis, und die Koeffizienten u und v — Bezout-Koeffizienten. Bézout-Koeffizienten werden effizient durch den erweiterten Euklid-Algorithmus berechnet. Diese Aussage wird auf Mengen natürlicher Zahlen verallgemeinert - ihre Bedeutung ist, dass die Untergruppe der von der Menge erzeugten Gruppe zyklisch ist und von einem Element erzeugt wird: ggT ( a 1 , a 2 , … , ein).

Berechnung des größten gemeinsamen Teilers (ggT).

Effiziente Möglichkeiten, den ggT zweier Zahlen zu berechnen, sind Euklids Algorithmus und binärAlgorithmus. Außerdem ist der GCD-Wert ( m,n) kann leicht berechnet werden, wenn die kanonische Entwicklung von Zahlen bekannt ist m und n für Primfaktoren:

wo sind verschiedene Primzahlen und und sind nicht-negative ganze Zahlen (sie können Null sein, wenn die entsprechende Primzahl nicht in der Zerlegung ist). Dann gcd ( m,n) und LCM ( m,n) werden durch die Formeln ausgedrückt:

Wenn es mehr als zwei Zahlen gibt: , wird ihr ggT nach folgendem Algorithmus ermittelt:

- Dies ist der gewünschte GCD.

Auch um zu finden größter gemeinsamer Teiler, kannst du jede der gegebenen Zahlen in Primfaktoren zerlegen. Schreiben Sie dann nur die Faktoren separat aus, die in allen angegebenen Zahlen enthalten sind. Dann multiplizieren wir die ausgeschriebenen Zahlen untereinander – das Ergebnis der Multiplikation ist der größte gemeinsame Teiler .

Analysieren wir Schritt für Schritt die Berechnung des größten gemeinsamen Teilers:

1. Zerlege die Teiler von Zahlen in Primfaktoren:

Berechnungen werden bequem mit einem vertikalen Balken geschrieben. Schreiben Sie links von der Zeile zuerst den Dividenden auf, rechts den Divisor. Weiter in der linken Spalte schreiben wir die Werte von privat auf. Lassen Sie es uns gleich an einem Beispiel erklären. Zerlegen wir die Zahlen 28 und 64 in Primfaktoren.

2. Wir unterstreichen in beiden Zahlen dieselben Primfaktoren:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Wir finden das Produkt identischer Primfaktoren und schreiben die Antwort auf:

ggT (28; 64) = 2. 2 = 4

Antwort: ggT (28; 64) = 4

Sie können die Position des GCD auf zwei Arten anordnen: in einer Spalte (wie oben) oder „in einer Zeile“.

Der erste Weg, GCD zu schreiben:

Finden Sie GCD 48 und 36.

ggT (48; 36) = 2 . 2. 3 = 12

Die zweite Möglichkeit, GCD zu schreiben:

Lassen Sie uns nun die GCD-Suchlösung in eine Zeile schreiben. Finden Sie GCD 10 und 15.

D(10) = (1, 2, 5, 10)

D(15) = (1, 3, 5, 15)

D(10, 15) = (1, 5)

Lassen Sie uns das Problem lösen. Wir haben zwei Arten von Cookies. Einige sind Schokolade und einige sind einfach. Es gibt 48 Schokoladenstücke und einfache 36. Aus diesen Keksen muss die größtmögliche Anzahl von Geschenken hergestellt werden, und alle müssen verwendet werden.

Zuerst schreiben wir alle Teiler jeder dieser beiden Zahlen auf, da diese beiden Zahlen durch die Anzahl der Geschenke teilbar sein müssen.

Wir bekommen

• 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
• 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Lassen Sie uns gemeinsame Teiler finden, die sowohl die erste als auch die zweite Zahl haben.

Gemeinsame Teiler sind: 1, 2, 3, 4, 6, 12.

Der größte gemeinsame Teiler von allen ist 12. Diese Zahl wird als größter gemeinsamer Teiler von 36 und 48 bezeichnet.

Anhand des Ergebnisses können wir schlussfolgern, dass aus allen Keksen 12 Geschenke gemacht werden können. Ein solches Geschenk enthält 4 Schokoladenkekse und 3 normale Kekse.

Suche nach dem größten gemeinsamen Teiler

• Die größte natürliche Zahl, durch die zwei Zahlen a und b ohne Rest teilbar sind, heißt größter gemeinsamer Teiler dieser Zahlen.

Manchmal wird die Abkürzung GCD verwendet, um den Eintrag abzukürzen.

Einige Zahlenpaare haben Eins als größten gemeinsamen Teiler. Solche Nummern werden angerufen teilerfremde Zahlen. Beispiel: Zahlen 24 und 35. Haben GCD = 1.

So finden Sie den größten gemeinsamen Teiler

Um den größten gemeinsamen Teiler zu finden, ist es nicht notwendig, alle Teiler dieser Zahlen aufzuschreiben.

Sie können auch anders. Zerlege zunächst beide Zahlen in Primfaktoren.

• 48 = 2*2*2*2*3,
• 36 = 2*2*3*3.

Nun streichen wir von den Faktoren, die in der Erweiterung der ersten Zahl enthalten sind, alle diejenigen, die nicht in der Erweiterung der zweiten Zahl enthalten sind. In unserem Fall sind dies zwei Zweien.

• 48 = 2*2*2*2*3 ,
• 36 = 2*2*3 *3.

Übrig bleiben die Faktoren 2, 2 und 3. Ihr Produkt ist 12. Diese Zahl ist der größte gemeinsame Teiler der Zahlen 48 und 36.

Diese Regel kann auf den Fall von drei, vier usw. erweitert werden. Zahlen.

Allgemeines Schema zum Finden des größten gemeinsamen Teilers

• 1. Zahlen in Primfaktoren zerlegen.
• 2. Streichen Sie von den Faktoren, die in der Erweiterung einer dieser Zahlen enthalten sind, diejenigen durch, die nicht in der Erweiterung anderer Zahlen enthalten sind.
• 3. Berechnen Sie das Produkt der verbleibenden Faktoren.

Finden des kleinsten gemeinsamen Vielfachen (LCM) und des größten gemeinsamen Teilers (ggT) natürlicher Zahlen.

	2						5
	2						5
	3						3
	5

60=2*2*3*5
75=3*5*5
2) Wir schreiben die in der Entwicklung der ersten dieser Zahlen enthaltenen Faktoren aus und ergänzen sie um den fehlenden Faktor 5 aus der Entwicklung der zweiten Zahl. Wir erhalten: 2*2*3*5*5=300. NOC gefunden, d.h. diese Summe = 300. Vergessen Sie nicht die Dimension und schreiben Sie die Antwort:
Antwort: Mama gibt jeweils 300 Rubel.

Definition von GCD: Größter gemeinsamer Teiler (ggT) natürliche Zahlen a und in Nennen Sie die größte natürliche Zahl c, wozu und a, und b ohne Rest geteilt. Jene. c ist die kleinste natürliche Zahl, für die und a und b sind Vielfache.

Erinnerung: Es gibt zwei Ansätze zur Definition natürlicher Zahlen

• Nummern verwendet in: Aufzählung (Nummerierung) von Elementen (erstes, zweites, drittes, ...); - in der Regel in Schulen.
• Angabe der Anzahl der Gegenstände (kein Pokemon - null, ein Pokemon, zwei Pokemon, ...).

Negative und nicht ganzzahlige (rationale, reelle, ...) Zahlen sind nicht natürlich. Einige Autoren nehmen die Null in die Menge der natürlichen Zahlen auf, andere nicht. Die Menge aller natürlichen Zahlen wird üblicherweise mit dem Symbol bezeichnet N

Erinnerung: Teiler einer natürlichen Zahl a ruf die nummer an b, zu welchem a ohne Rest geteilt. Vielfache der natürlichen Zahl b eine natürliche Zahl genannt a, die geteilt wird durch b ohne jede Spur. Wenn Zahl b- Zahlenteiler a, dann a mehrere von b. Beispiel: 2 ist ein Teiler von 4 und 4 ist ein Vielfaches von 2. 3 ist ein Teiler von 12 und 12 ist ein Vielfaches von 3.
Erinnerung: Natürliche Zahlen heißen Primzahlen, wenn sie nur durch sich selbst und durch 1 ohne Rest teilbar sind. Teilerfremde sind Zahlen, die nur einen gemeinsamen Teiler gleich 1 haben.

Definition, wie man den GCD im allgemeinen Fall findet: So finden Sie ggT (größter gemeinsamer Teiler) Es werden mehrere natürliche Zahlen benötigt:
1) Zerlege sie in Primfaktoren. (Die Primzahltabelle kann dabei sehr hilfreich sein.)
2) Schreiben Sie die Faktoren auf, die in der Erweiterung von einem von ihnen enthalten sind.
3) Löschen Sie diejenigen, die nicht in der Erweiterung der verbleibenden Zahlen enthalten sind.
4) Multiplizieren Sie die in Absatz 3) erhaltenen Faktoren.

Aufgabe 2 auf (NIO): Bis zum Jahreswechsel kaufte Kolya Puzatov 48 Hamster und 36 Kaffeekannen in der Stadt. Fekla Dormidontova bekam als ehrlichstes Mädchen der Klasse die Aufgabe, diesen Besitz in möglichst viele Geschenksets für Lehrer aufzuteilen. Wie hoch ist die Anzahl der Sets? Wie ist die Zusammensetzung der Sets?

Beispiel 2.1. Lösung des Problems, GCD zu finden. GCD durch Auswahl finden.
Entscheidung: Jede der Zahlen 48 und 36 muss durch die Anzahl der Geschenke teilbar sein.
1) Schreibe die Teiler 48 auf: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) Schreibe die Teiler 36 auf: 36, 18, 12 , 9, 6, 3, 2, 1 Wähle den größten gemeinsamen Teiler. Op-la-la! Gefunden, das ist die Anzahl der Sätze von 12 Stück.
3) Teilen Sie 48 durch 12, wir erhalten 4, teilen Sie 36 durch 12, wir erhalten 3. Vergessen Sie die Dimension nicht und schreiben Sie die Antwort:
Antwort: Sie erhalten 12 Sets mit 4 Hamstern und 3 Kaffeekannen in jedem Set.

Das kleinste gemeinsame Vielfache zweier Zahlen steht in direktem Zusammenhang mit dem größten gemeinsamen Teiler dieser Zahlen. Das Verbindung zwischen GCD und NOC ist durch den folgenden Satz definiert.

Satz.

Das kleinste gemeinsame Vielfache zweier positiver ganzer Zahlen a und b ist gleich dem Produkt der Zahlen a und b dividiert durch den größten gemeinsamen Teiler der Zahlen a und b , d. h. LCM(a, b)=a b: ggT(a, b).

Nachweisen.

Lassen M ist ein Vielfaches der Zahlen a und b. Das heißt, M ist durch a teilbar, und gemäß der Definition der Teilbarkeit gibt es eine ganze Zahl k, so dass die Gleichheit M = a·k wahr ist. Aber M ist auch durch b teilbar, dann ist a k durch b teilbar.

Bezeichne ggT(a, b) als d . Dann können wir die Gleichungen a=a 1 ·d und b=b 1 ·d aufschreiben, und a 1 =a:d und b 1 =b:d werden teilerfremde Zahlen sein. Daher kann die im vorherigen Absatz erhaltene Bedingung, dass a k durch b teilbar ist, wie folgt umformuliert werden: a 1 d k ist durch b 1 d teilbar, und dies ist aufgrund der Teilbarkeitseigenschaften äquivalent zu der Bedingung, dass a 1 k durch b eins teilbar ist.

Wir müssen auch zwei wichtige Folgerungen aus dem betrachteten Theorem aufschreiben.

Gemeinsame Vielfache zweier Zahlen sind gleich Vielfache ihres kleinsten gemeinsamen Vielfachen.

Dies ist wahr, da jedes gemeinsame Vielfache von M Zahlen a und b durch die Gleichheit M=LCM(a, b) t für einen ganzzahligen Wert t definiert ist.

Das kleinste gemeinsame Vielfache der teilerfremden positiven Zahlen a und b ist gleich ihrem Produkt.

Der Grund für diese Tatsache ist ziemlich offensichtlich. Da a und b teilerfremd sind, ist ggT(a, b)=1 , also LCM(a, b)=a b: GCD(a, b)=a b:1=a b.

Kleinstes gemeinsames Vielfaches von drei oder mehr Zahlen

Das Finden des kleinsten gemeinsamen Vielfachen von drei oder mehr Zahlen kann auf das sukzessive Finden des LCM von zwei Zahlen reduziert werden. Wie das geht, zeigt der folgende Satz: a 1 , a 2 , …, a k stimmen mit gemeinsamen Vielfachen der Zahlen m k-1 überein und a k stimmen also mit Vielfachen von m k überein. Und da das kleinste positive Vielfache der Zahl m k die Zahl m k selbst ist, dann ist das kleinste gemeinsame Vielfache der Zahlen a 1 , a 2 , …, a k m k .

Referenzliste.

• Wilenkin N.Ja. usw. Mathematik. Klasse 6: Lehrbuch für Bildungseinrichtungen.
• Winogradov I. M. Grundlagen der Zahlentheorie.
• Michelowitsch Sh.Kh. Zahlentheorie.
• Kulikov L. Ya. ua Aufgabensammlung der Algebra und Zahlentheorie: Lehrbuch für Studierende der fiz.-mat. Spezialgebiete pädagogischer Institute.

Dieser Artikel ist über Finden des größten gemeinsamen Teilers (ggT) zwei oder mehr Zahlen. Betrachten Sie zuerst den Euklid-Algorithmus, mit dem Sie den ggT zweier Zahlen finden können. Danach werden wir uns mit einer Methode befassen, mit der wir den ggT von Zahlen als Produkt ihrer gemeinsamen Primfaktoren berechnen können. Als nächstes werden wir uns damit befassen, den größten gemeinsamen Teiler von drei oder mehr Zahlen zu finden, und auch Beispiele für die Berechnung des ggT negativer Zahlen geben.

Seitennavigation.

Euklids Algorithmus zum Finden von GCD

Beachten Sie, dass wir, wenn wir uns von Anfang an der Tabelle der Primzahlen zugewandt hätten, herausgefunden hätten, dass die Zahlen 661 und 113 Primzahlen sind, woraus wir sofort sagen könnten, dass ihr größter gemeinsamer Teiler 1 ist.

Antworten:

gcd(661, 113)=1 .

Ermitteln von ggT durch Faktorisieren von Zahlen in Primfaktoren

Ziehen Sie einen anderen Weg in Betracht, um den GCD zu finden. Den größten gemeinsamen Teiler erhält man, indem man Zahlen in Primfaktoren zerlegt. Formulieren wir die Regel: Der ggT zweier positiver ganzer Zahlen a und b ist gleich dem Produkt aller gemeinsamen Primfaktoren bei der Faktorisierung von a und b in Primfaktoren.

Lassen Sie uns ein Beispiel geben, um die Regel zum Finden des GCD zu erklären. Teilen Sie uns die Erweiterungen der Zahlen 220 und 600 in Primfaktoren mit, sie haben die Form 220=2 2 5 11 und 600=2 2 2 3 5 5 . Gemeinsame Primfaktoren, die an der Erweiterung der Zahlen 220 und 600 beteiligt sind, sind 2, 2 und 5. Also ggT(220, 600)=2 2 5=20 .

Wenn wir also die Zahlen a und b in Primfaktoren zerlegen und das Produkt aller ihrer gemeinsamen Faktoren finden, dann wird dies den größten gemeinsamen Teiler der Zahlen a und b finden.

Betrachten Sie ein Beispiel für das Finden des GCD gemäß der angekündigten Regel.

Beispiel.

Finde den größten gemeinsamen Teiler von 72 und 96.

Entscheidung.

Zerlegen wir die Zahlen 72 und 96:

Das heißt, 72 = 2 2 2 3 3 und 96 = 2 2 2 2 2 3 . Übliche Primfaktoren sind 2 , 2 , 2 und 3 . Also ggT(72, 96)=2 2 2 3=24 .

Antworten:

gcd(72, 96)=24 .

Zum Abschluss dieses Abschnitts stellen wir fest, dass die Gültigkeit der obigen Regel zum Ermitteln des ggT aus der Eigenschaft des größten gemeinsamen Teilers folgt, die dies besagt ggT(m a 1 , m b 1)=m ggT(a 1 , b 1), wobei m eine beliebige positive ganze Zahl ist.

GCD von drei oder mehr Zahlen finden

Das Finden des größten gemeinsamen Teilers von drei oder mehr Zahlen kann auf das sukzessive Finden des ggT von zwei Zahlen reduziert werden. Wir haben dies bei der Untersuchung der Eigenschaften von GCD erwähnt. Dort haben wir den Satz formuliert und bewiesen: Der größte gemeinsame Teiler mehrerer Zahlen a 1 , a 2 , …, a k ist gleich der Zahl d k , die sich bei der sequentiellen Berechnung von ggT(a 1 , a 2)=d 2 ergibt , ggT(d 2 , a 3) =d 3 , ggT(d 3 , a 4)=d 4 , …, ggT(d k-1 , a k)=d k .

Sehen wir uns an, wie der Prozess zum Ermitteln des ggT mehrerer Zahlen aussieht, indem wir die Lösung des Beispiels betrachten.

Beispiel.

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

Entscheidung.

In diesem Beispiel a 1 =78 , a 2 =294 , a 3 =570 , a 4 =36 .

Zunächst bestimmen wir mit dem Euklid-Algorithmus den größten gemeinsamen Teiler d 2 der ersten beiden Zahlen 78 und 294 . Beim Dividieren erhalten wir die Gleichungen 294=78 3+60 ; 78=60 1+18 ; 60=18 3+6 und 18=6 3 . Somit ist d 2 =GCD(78, 294)=6 .

Jetzt rechnen wir d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Wieder wenden wir den Euklid-Algorithmus an: 570=6·95 , also d 3 =GCD(6, 570)=6 .

Es bleibt zu rechnen d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Da 36 durch 6 teilbar ist, ist d 4 \u003d GCD (6, 36) \u003d 6.

Der größte gemeinsame Teiler der vier gegebenen Zahlen ist also d 4 =6 , also ggT(78, 294, 570, 36)=6 .

Antworten:

ggT(78, 294, 570, 36)=6 .

Durch die Zerlegung von Zahlen in Primfaktoren können Sie auch den ggT von drei oder mehr Zahlen berechnen. In diesem Fall ergibt sich der größte gemeinsame Teiler als Produkt aller gemeinsamen Primfaktoren der gegebenen Zahlen.

Beispiel.

Berechnen Sie den ggT der Zahlen aus dem vorherigen Beispiel unter Verwendung ihrer Primfaktorzerlegungen.

Entscheidung.

Zerlegen wir die Zahlen 78 , 294 , 570 und 36 in Primfaktoren, erhalten wir 78=2 3 13 , 294=2 3 7 7 , 570=2 3 5 19 , 36=2 2 3 .3 . Die gemeinsamen Primfaktoren aller gegebenen vier Zahlen sind die Zahlen 2 und 3. Somit, GCD(78, 294, 570, 36)=2 3=6.