Um zu lernen, wie man den größten gemeinsamen Teiler zweier oder mehrerer Zahlen ermittelt, müssen Sie verstehen, was natürliche, primäre und komplexe Zahlen sind.

Eine natürliche Zahl ist jede Zahl, die zum Zählen ganzer Objekte verwendet wird.

Wenn eine natürliche Zahl nur in sich selbst und eins teilbar ist, nennt man sie Primzahl.

Alle natürlichen Zahlen können durch sich selbst und eins geteilt werden, aber die einzige gerade Primzahl ist 2, alle anderen können durch zwei geteilt werden. Daher können nur ungerade Zahlen Primzahlen sein.

Es gibt eine ganze Reihe von Primzahlen; eine vollständige Liste davon gibt es nicht. Um GCD zu finden, ist es praktisch, spezielle Tabellen mit solchen Zahlen zu verwenden.

Die meisten natürlichen Zahlen können nicht nur durch eins selbst, sondern auch durch andere Zahlen geteilt werden. So kann beispielsweise die Zahl 15 durch weitere 3 und 5 geteilt werden. Alle werden als Teiler der Zahl 15 bezeichnet.

Der Teiler eines beliebigen A ist also die Zahl, durch die es ohne Rest geteilt werden kann. Wenn eine Zahl mehr als zwei natürliche Faktoren hat, wird sie zusammengesetzt genannt.

Die Zahl 30 kann Teiler wie 1, 3, 5, 6, 15, 30 haben.

Sie werden feststellen, dass 15 und 30 die gleichen Teiler 1, 3, 5, 15 haben. Der größte gemeinsame Teiler dieser beiden Zahlen ist 15.

Somit ist der gemeinsame Teiler der Zahlen A und B die Zahl, durch die sie vollständig geteilt werden können. Die größte kann als die maximale Gesamtzahl angesehen werden, durch die sie geteilt werden kann.

Zur Lösung von Problemen wird die folgende Kurzinschrift verwendet:

GCD (A; B).

Beispiel: gcd (15; 30) = 30.

Um alle Teiler einer natürlichen Zahl aufzuschreiben, verwenden Sie die Notation:

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

GCD (9; 15) = 1

In diesem Beispiel haben die natürlichen Zahlen nur einen gemeinsamen Teiler. Sie werden relativ prim genannt, daher ist Eins ihr größter gemeinsamer Teiler.

So finden Sie den größten gemeinsamen Teiler von Zahlen

Um den gcd mehrerer Zahlen zu ermitteln, benötigen Sie:

Finden Sie alle Teiler jeder natürlichen Zahl einzeln, d. h. faktorisieren Sie sie in Faktoren (Primzahlen);

Wählen Sie alle identischen Faktoren gegebener Zahlen aus;

Multiplizieren Sie sie miteinander.

Um beispielsweise den größten gemeinsamen Teiler der Zahlen 30 und 56 zu berechnen, würden Sie Folgendes schreiben:

Um Verwirrung zu vermeiden, empfiehlt es sich, Faktoren in vertikalen Spalten zu schreiben. Auf der linken Seite der Linie müssen Sie den Dividenden und auf der rechten Seite den Divisor platzieren. Unter der Dividende sollten Sie den resultierenden Quotienten angeben.

In der rechten Spalte befinden sich also alle für die Lösung erforderlichen Faktoren.

Identische Teiler (gefundene Faktoren) können der Einfachheit halber unterstrichen werden. Sie sollten umgeschrieben und multipliziert und der größte gemeinsame Teiler notiert werden.

GCD (30; 56) = 2 * 5 = 10

So einfach ist es wirklich, den größten gemeinsamen Teiler von Zahlen zu finden. Wenn Sie ein wenig üben, können Sie dies fast automatisch tun.

Viele natürliche Zahlen sind aber auch durch andere natürliche Zahlen teilbar.

Zum Beispiel:

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

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

Man nennt die Zahlen, durch die die Zahl durch ein Ganzes teilbar ist (für 12 sind das 1, 2, 3, 4, 6 und 12). Teiler von Zahlen. Teiler einer natürlichen Zahl A- ist eine natürliche Zahl, die eine gegebene Zahl teilt A ohne jede Spur. Eine natürliche Zahl, die mehr als zwei Teiler hat, heißt zusammengesetzt .

Bitte beachten Sie, dass die Zahlen 12 und 36 gemeinsame Faktoren haben. Diese Zahlen sind: 1, 2, 3, 4, 6, 12. Der größte Teiler dieser Zahlen ist 12. Der gemeinsame Teiler dieser beiden Zahlen A Und B- Dies ist die Zahl, durch die beide gegebenen Zahlen ohne Rest geteilt werden A Und B.

Gemeinsame Vielfache Mehrere Zahlen ist eine Zahl, die durch jede dieser Zahlen teilbar ist. Zum Beispiel, die Zahlen 9, 18 und 45 haben ein gemeinsames Vielfaches von 180. Aber auch 90 und 360 sind ihre gemeinsamen Vielfachen. Unter allen gemeinsamen Vielfachen gibt es immer ein kleinstes, in diesem Fall ist es 90. Diese Zahl heißt das kleinstegemeinsames Vielfaches (CMM).

Die LCM ist immer eine natürliche Zahl, die größer sein muss als die größte der Zahlen, für die sie definiert ist.

Kleinstes gemeinsames Vielfaches (LCM). Eigenschaften.

Kommutativität:

Assoziativität:

Insbesondere wenn und Koprimzahlen sind, dann gilt:

Kleinstes gemeinsames Vielfaches zweier ganzer Zahlen M Und N ist ein Teiler aller anderen gemeinsamen Vielfachen M Und N. Darüber hinaus die Menge der gemeinsamen Vielfachen m, n stimmt mit der Menge der Vielfachen des LCM( überein m, n).

Die Asymptotik für kann durch einige zahlentheoretische Funktionen ausgedrückt werden.

Also, Tschebyscheff-Funktion. Und auch:

Dies ergibt sich aus der Definition und den Eigenschaften der Landau-Funktion g(n).

Was folgt aus dem Gesetz der Verteilung der Primzahlen?

Ermitteln des kleinsten gemeinsamen Vielfachen (LCM).

NOC( a, b) kann auf verschiedene Arten berechnet werden:

1. Wenn der größte gemeinsame Teiler bekannt ist, können Sie seinen Zusammenhang mit dem LCM nutzen:

2. Die kanonische Zerlegung beider Zahlen in Primfaktoren sei bekannt:

Wo p 1 ,...,p k- verschiedene Primzahlen und d 1 ,...,d k Und e 1 ,...,e k– nichtnegative ganze Zahlen (sie können Nullen sein, wenn die entsprechende Primzahl nicht in der Erweiterung enthalten ist).

Dann NOC ( A,B) wird nach der Formel berechnet:

Mit anderen Worten: Die LCM-Zerlegung enthält alle Primfaktoren, die in mindestens einer der Zahlenzerlegungen enthalten sind a, b, und der größte der beiden Exponenten dieses Multiplikators wird genommen.

Beispiel:

Die Berechnung des kleinsten gemeinsamen Vielfachen mehrerer Zahlen kann auf mehrere aufeinanderfolgende Berechnungen des LCM zweier Zahlen reduziert werden:

Regel. Um den LCM einer Zahlenreihe zu ermitteln, benötigen Sie:

- Zahlen in Primfaktoren zerlegen;

- Übertragen Sie die größte Zerlegung (das Produkt der Faktoren der größten Anzahl der gegebenen) auf die Faktoren des gewünschten Produkts und fügen Sie dann Faktoren aus der Zerlegung anderer Zahlen hinzu, die nicht in der ersten Zahl vorkommen oder darin vorkommen seltener;

— Das resultierende Produkt der Primfaktoren ist das kgV der gegebenen Zahlen.

Zwei oder mehr natürliche Zahlen haben ihr eigenes LCM. Wenn die Zahlen keine Vielfachen voneinander sind oder in der Entwicklung nicht die gleichen Faktoren haben, ist ihr kgV gleich dem Produkt dieser Zahlen.

Die Primfaktoren der Zahl 28 (2, 2, 7) werden mit einem Faktor 3 (der Zahl 21) ergänzt, das resultierende Produkt (84) ist die kleinste Zahl, die durch 21 und 28 teilbar ist.

Die Primfaktoren der größten Zahl 30 werden durch den Faktor 5 der Zahl 25 ergänzt, das resultierende Produkt 150 ist größer als die größte Zahl 30 und durch alle gegebenen Zahlen ohne Rest teilbar. Dies ist das kleinstmögliche Produkt (150, 250, 300...), das ein Vielfaches aller gegebenen Zahlen ist.

Die Zahlen 2,3,11,37 sind Primzahlen, daher ist ihr kgV gleich dem Produkt der gegebenen Zahlen.

Regel. Um den kgV von Primzahlen zu berechnen, müssen Sie alle diese Zahlen miteinander multiplizieren.

Andere Option:

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

1) Stellen Sie jede Zahl als Produkt ihrer Primfaktoren dar, zum Beispiel:

504 = 2 2 2 3 3 7,

2) Schreiben Sie die Potenzen aller Primfaktoren auf:

504 = 2 2 2 3 3 7 = 2 3 3 2 7 1,

3) Notieren Sie alle Primteiler (Multiplikatoren) jeder dieser Zahlen;

4) Wählen Sie den höchsten Grad jeder dieser Zahlen, der in allen Erweiterungen dieser Zahlen zu finden ist;

5) Multiplizieren Sie diese Kräfte.

Beispiel. Finden Sie den LCM der Zahlen: 168, 180 und 3024.

Lösung. 168 = 2 2 2 3 7 = 2 3 3 1 7 1,

180 = 2 2 3 3 5 = 2 2 3 2 5 1,

3024 = 2 2 2 2 3 3 3 7 = 2 4 3 3 7 1.

Wir schreiben die größten Potenzen aller Primteiler auf und multiplizieren sie:

NOC = 2 4 3 3 5 1 7 1 = 15120.

LCM – kleinstes gemeinsames Vielfaches. Eine Zahl, die alle gegebenen Zahlen ohne Rest dividiert.

Wenn die angegebenen Zahlen beispielsweise 2, 3, 5 sind, dann ist LCM=2*3*5=30

Und wenn die angegebenen Zahlen 2,4,8 sind, dann ist LCM =8

Was ist GCD?

GCD ist der größte gemeinsame Teiler. Eine Zahl, mit der jede der angegebenen Zahlen dividiert werden kann, ohne dass ein Rest verbleibt.

Es ist logisch, dass, wenn die gegebenen Zahlen Primzahlen sind, der ggT gleich eins ist.

Und wenn die angegebenen Zahlen 2, 4, 8 sind, dann ist GCD gleich 2.

Wir werden es nicht allgemein beschreiben, sondern die Lösung lediglich anhand eines Beispiels zeigen.

Gegeben sind zwei Zahlen 126 und 44. Finden Sie GCD.

Dann erhalten wir zwei Zahlen der Form

Dann wird GCD berechnet als

wobei min der Minimalwert aller Potenzen der Zahl pn ist

und NOC als

Dabei ist max der Maximalwert aller Potenzen der Zahl pn

Wenn Sie sich die obigen Formeln ansehen, können Sie leicht beweisen, dass der ggT von zwei oder mehr Zahlen gleich eins ist, wenn es unter mindestens einem Paar gegebener Werte relativ Primzahlen gibt.

Daher ist es einfach, die Frage zu beantworten, was der ggT von Zahlen wie 3, 25412, 3251, 7841, 25654, 7 ist, ohne etwas zu berechnen.

Die Zahlen 3 und 7 sind teilerfremd, daher ist ggT = 1

Schauen wir uns ein Beispiel an.

Gegeben seien die drei Zahlen 24654, 25473 und 954

Jede Zahl wird in die folgenden Faktoren zerlegt

Oder wenn wir es in einer alternativen Form schreiben

Das heißt, der ggT dieser drei Zahlen ist gleich drei

Nun, wir können den LCM auf ähnliche Weise berechnen und er ist gleich

Unser Bot hilft Ihnen bei der Berechnung des GCD und LCM aller ganzen Zahlen, zwei, drei oder zehn.

Finden wir den größten gemeinsamen Teiler von GCD (36; 24)

Lösungsschritte

Methode Nr. 1

36 - zusammengesetzte Zahl
24 - zusammengesetzte Zahl

Erweitern wir die Zahl 36

36: 2 = 18
18: 2 = 9 - teilbar durch die Primzahl 2
9: 3 = 3 - teilbar durch die Primzahl 3.

Lassen Sie uns die Zahl 24 aufschlüsseln in Primfaktoren zerlegen und grün markieren. Wir beginnen mit der Auswahl eines Teilers aus Primzahlen, beginnend mit der kleinsten Primzahl 2, bis sich herausstellt, dass der Quotient eine Primzahl ist

24: 2 = 12 - teilbar durch die Primzahl 2
12: 2 = 6 - teilbar durch die Primzahl 2
6: 2 = 3
Wir schließen die Division ab, da 3 eine Primzahl ist

2) Markieren Sie es blau und notieren Sie die gemeinsamen Faktoren

36 = 2 ⋅ 2 ⋅ 3 ⋅ 3
24 = 2 ⋅ 2 ⋅ 2 ⋅ 3
Gemeinsame Faktoren (36; 24): 2, 2, 3

3) Um nun den GCD zu ermitteln, müssen Sie die gemeinsamen Faktoren multiplizieren

Antwort: GCD (36; 24) = 2 ∙ 2 ∙ 3 ​​​​= 12

Methode Nr. 2

1) Finden Sie alle möglichen Teiler der Zahlen (36; 24). Dazu teilen wir abwechselnd die Zahl 36 in Teiler von 1 bis 36 und die Zahl 24 in Teiler von 1 bis 24. Ist die Zahl ohne Rest teilbar, dann schreiben wir den Teiler in die Liste der Teiler.

Für Nummer 36
36: 1 = 36; 36: 2 = 18; 36: 3 = 12; 36: 4 = 9; 36: 6 = 6; 36: 9 = 4; 36: 12 = 3; 36: 18 = 2; 36: 36 = 1;

Für die Nummer 24 Schreiben wir alle Fälle auf, in denen es ohne Rest teilbar ist:
24: 1 = 24; 24: 2 = 12; 24: 3 = 8; 24: 4 = 6; 24: 6 = 4; 24: 8 = 3; 24: 12 = 2; 24: 24 = 1;

2) Schreiben wir alle gemeinsamen Teiler der Zahlen (36; 24) auf und markieren den größten grün. Dies ist der größte gemeinsame Teiler des ggT der Zahlen (36; 24).

Gemeinsame Faktoren der Zahlen (36; 24): 1, 2, 3, 4, 6, 12

Antwort: GCD (36 ; 24) = 12

Finden wir das kleinste gemeinsame Vielfache des LCM (52; 49)

Lösungsschritte

Methode Nr. 1

1) Zerlegen wir die Zahlen in Primfaktoren. Dazu prüfen wir, ob jede der Zahlen eine Primzahl ist (wenn eine Zahl eine Primzahl ist, kann sie nicht in Primfaktoren zerlegt werden, sondern ist selbst eine Zerlegung).

52 - zusammengesetzte Zahl
49 - zusammengesetzte Zahl

Erweitern wir die Zahl 52 in Primfaktoren zerlegen und grün markieren. Wir beginnen mit der Auswahl eines Teilers aus Primzahlen, beginnend mit der kleinsten Primzahl 2, bis sich herausstellt, dass der Quotient eine Primzahl ist

52: 2 = 26 - teilbar durch die Primzahl 2
26: 2 = 13 - teilbar durch die Primzahl 2.
Wir schließen die Division ab, da 13 eine Primzahl ist

Erweitern wir die Zahl 49 in Primfaktoren zerlegen und grün markieren. Wir beginnen mit der Auswahl eines Teilers aus Primzahlen, beginnend mit der kleinsten Primzahl 2, bis sich herausstellt, dass der Quotient eine Primzahl ist

49: 7 = 7 - teilbar durch die Primzahl 7.
Wir schließen die Division ab, da 7 eine Primzahl ist

2) Notieren Sie zunächst die Faktoren der größten Zahl und dann die der kleineren Zahl. Suchen wir die fehlenden Faktoren und markieren Sie in der Erweiterung der kleineren Zahl die Faktoren blau, die in der Erweiterung der größeren Zahl nicht enthalten waren.

52 = 2 ∙ 2 ∙ 13
49 = 7 ∙ 7

3) Um nun den LCM zu ermitteln, müssen Sie die Faktoren der größeren Zahl mit den fehlenden Faktoren multiplizieren, die blau hervorgehoben sind

LCM (52 ; 49) = 2 ∙ 2 ∙ 13 ∙ 7 ∙ 7 = 2548

Methode Nr. 2

1) Finden Sie alle möglichen Vielfachen der Zahlen (52; 49). Dazu multiplizieren wir abwechselnd die Zahl 52 mit den Zahlen von 1 bis 49 und die Zahl 49 mit den Zahlen von 1 bis 52.

Wählen Sie alle Vielfachen aus 52 in Grün:

52 ∙ 1 = 52 ; 52 ∙ 2 = 104 ; 52 ∙ 3 = 156 ; 52 ∙ 4 = 208 ;
52 ∙ 5 = 260 ; 52 ∙ 6 = 312 ; 52 ∙ 7 = 364 ; 52 ∙ 8 = 416 ;
52 ∙ 9 = 468 ; 52 ∙ 10 = 520 ; 52 ∙ 11 = 572 ; 52 ∙ 12 = 624 ;
52 ∙ 13 = 676 ; 52 ∙ 14 = 728 ; 52 ∙ 15 = 780 ; 52 ∙ 16 = 832 ;
52 ∙ 17 = 884 ; 52 ∙ 18 = 936 ; 52 ∙ 19 = 988 ; 52 ∙ 20 = 1040 ;
52 ∙ 21 = 1092 ; 52 ∙ 22 = 1144 ; 52 ∙ 23 = 1196 ; 52 ∙ 24 = 1248 ;
52 ∙ 25 = 1300 ; 52 ∙ 26 = 1352 ; 52 ∙ 27 = 1404 ; 52 ∙ 28 = 1456 ;
52 ∙ 29 = 1508 ; 52 ∙ 30 = 1560 ; 52 ∙ 31 = 1612 ; 52 ∙ 32 = 1664 ;
52 ∙ 33 = 1716 ; 52 ∙ 34 = 1768 ; 52 ∙ 35 = 1820 ; 52 ∙ 36 = 1872 ;
52 ∙ 37 = 1924 ; 52 ∙ 38 = 1976 ; 52 ∙ 39 = 2028 ; 52 ∙ 40 = 2080 ;
52 ∙ 41 = 2132 ; 52 ∙ 42 = 2184 ; 52 ∙ 43 = 2236 ; 52 ∙ 44 = 2288 ;
52 ∙ 45 = 2340 ; 52 ∙ 46 = 2392 ; 52 ∙ 47 = 2444 ; 52 ∙ 48 = 2496 ;
52 ∙ 49 = 2548 ;

Wählen Sie alle Vielfachen aus 49 in Grün:

49 ∙ 1 = 49 ; 49 ∙ 2 = 98 ; 49 ∙ 3 = 147 ; 49 ∙ 4 = 196 ;
49 ∙ 5 = 245 ; 49 ∙ 6 = 294 ; 49 ∙ 7 = 343 ; 49 ∙ 8 = 392 ;
49 ∙ 9 = 441 ; 49 ∙ 10 = 490 ; 49 ∙ 11 = 539 ; 49 ∙ 12 = 588 ;
49 ∙ 13 = 637 ; 49 ∙ 14 = 686 ; 49 ∙ 15 = 735 ; 49 ∙ 16 = 784 ;
49 ∙ 17 = 833 ; 49 ∙ 18 = 882 ; 49 ∙ 19 = 931 ; 49 ∙ 20 = 980 ;
49 ∙ 21 = 1029 ; 49 ∙ 22 = 1078 ; 49 ∙ 23 = 1127 ; 49 ∙ 24 = 1176 ;
49 ∙ 25 = 1225 ; 49 ∙ 26 = 1274 ; 49 ∙ 27 = 1323 ; 49 ∙ 28 = 1372 ;
49 ∙ 29 = 1421 ; 49 ∙ 30 = 1470 ; 49 ∙ 31 = 1519 ; 49 ∙ 32 = 1568 ;
49 ∙ 33 = 1617 ; 49 ∙ 34 = 1666 ; 49 ∙ 35 = 1715 ; 49 ∙ 36 = 1764 ;
49 ∙ 37 = 1813 ; 49 ∙ 38 = 1862 ; 49 ∙ 39 = 1911 ; 49 ∙ 40 = 1960 ;
49 ∙ 41 = 2009 ; 49 ∙ 42 = 2058 ; 49 ∙ 43 = 2107 ; 49 ∙ 44 = 2156 ;
49 ∙ 45 = 2205 ; 49 ∙ 46 = 2254 ; 49 ∙ 47 = 2303 ; 49 ∙ 48 = 2352 ;
49 ∙ 49 = 2401 ; 49 ∙ 50 = 2450 ; 49 ∙ 51 = 2499 ; 49 ∙ 52 = 2548 ;

2) Schreiben wir alle gemeinsamen Vielfachen der Zahlen (52; 49) auf und markieren das kleinste grün. Dies ist das kleinste gemeinsame Vielfache der Zahlen (52; 49).

Gemeinsame Vielfache von Zahlen (52; 49): 2548

Antwort: LCM (52; 49) = 2548

Größter gemeinsamer Teiler

Definition 2

Wenn eine natürliche Zahl a durch eine natürliche Zahl $b$ teilbar ist, dann heißt $b$ Teiler von $a$ und $a$ heißt Vielfaches von $b$.

Seien $a$ und $b$ natürliche Zahlen. Die Zahl $c$ wird als gemeinsamer Teiler von $a$ und $b$ bezeichnet.

Die Menge der gemeinsamen Teiler der Zahlen $a$ und $b$ ist endlich, da keiner dieser Teiler größer als $a$ sein kann. Das bedeutet, dass es unter diesen Teilern einen größten gibt, der als größter gemeinsamer Teiler der Zahlen $a$ und $b$ bezeichnet wird und durch die folgende Notation bezeichnet wird:

$GCD\(a;b)\ oder \D\(a;b)$

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

1. Finden Sie das Produkt der in Schritt 2 gefundenen Zahlen. Die resultierende Zahl ist der gewünschte größte gemeinsame Teiler.

Beispiel 1

Finden Sie den ggT der Zahlen $121$ und $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Wählen Sie die Zahlen aus, die in der Erweiterung dieser Zahlen enthalten sind

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Finden Sie das Produkt der in Schritt 2 gefundenen Zahlen. Die resultierende Zahl ist der gewünschte größte gemeinsame Teiler.

$GCD=2\cdot 11=22$

Beispiel 2

Finden Sie den ggT der Monome $63$ und $81$.

Wir werden nach dem vorgestellten Algorithmus finden. Dafür:

Zerlegen wir die Zahlen in Primfaktoren

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Wir wählen die Zahlen aus, die in der Erweiterung dieser Zahlen enthalten sind

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Lassen Sie uns das Produkt der in Schritt 2 ermittelten Zahlen ermitteln. Die resultierende Zahl ist der gewünschte größte gemeinsame Teiler.

$GCD=3\cdot 3=9$

Sie können den ggT zweier Zahlen auf andere Weise ermitteln, indem Sie eine Reihe von Teilern von Zahlen verwenden.

Beispiel 3

Finden Sie den ggT der Zahlen $48$ und $60$.

Lösung:

Finden wir die Menge der Teiler der Zahl $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Finden wir nun die Menge der Teiler der Zahl $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\) $

Finden wir den Schnittpunkt dieser Mengen: $\left\((\rm 1,2,3,4,6,12)\right\)$ – diese Menge bestimmt die Menge der gemeinsamen Teiler der Zahlen $48$ und $60 $. Das größte Element in dieser Menge ist die Zahl $12$. Das bedeutet, dass der größte gemeinsame Teiler der Zahlen $48$ und $60$ $12$ ist.

Definition von NPL

Definition 3

Gemeinsame Vielfache natürlicher Zahlen$a$ und $b$ ist eine natürliche Zahl, die ein Vielfaches von $a$ und $b$ ist.

Gemeinsame Vielfache von Zahlen sind Zahlen, die ohne Rest durch die ursprünglichen Zahlen teilbar sind. Beispielsweise sind für die Zahlen 25 $ und 50 $ die gemeinsamen Vielfachen die Zahlen 50.100, 150.200 $ usw.

Das kleinste gemeinsame Vielfache wird als kleinstes gemeinsames Vielfaches bezeichnet und mit LCM$(a;b)$ oder K$(a;b).$ bezeichnet

Um den LCM zweier Zahlen zu ermitteln, müssen Sie:

1. Faktorisieren Sie Zahlen in Primfaktoren
2. Schreiben Sie die Faktoren auf, die Teil der ersten Zahl sind, und addieren Sie dazu die Faktoren, die Teil der zweiten, aber nicht Teil der ersten Zahl sind

Beispiel 4

Finden Sie den LCM der Zahlen $99$ und $77$.

Wir werden nach dem vorgestellten Algorithmus finden. Dafür

Faktorisieren Sie Zahlen in Primfaktoren

$99=3\cdot 3\cdot 11$

Schreiben Sie die im ersten Schritt enthaltenen Faktoren auf

Fügen Sie ihnen Multiplikatoren hinzu, die Teil des zweiten und nicht Teil des ersten sind

Finden Sie das Produkt der in Schritt 2 gefundenen Zahlen. Die resultierende Zahl ist das gewünschte kleinste gemeinsame Vielfache

$NOK=3\cdot 3\cdot 11\cdot 7=693$

Das Zusammenstellen von Listen mit Teilern von Zahlen ist oft eine sehr arbeitsintensive Aufgabe. Es gibt eine Möglichkeit, GCD zu finden, den sogenannten Euklidischen Algorithmus.

Aussagen, auf denen der Euklidische Algorithmus basiert:

Wenn $a$ und $b$ natürliche Zahlen sind und $a\vdots b$, dann ist $D(a;b)=b$

Wenn $a$ und $b$ natürliche Zahlen sind, so dass $b

Mit $D(a;b)= D(a-b;b)$ können wir die betrachteten Zahlen sukzessive reduzieren, bis wir ein Zahlenpaar erreichen, bei dem eine von ihnen durch die andere teilbar ist. Dann ist die kleinere dieser Zahlen der gewünschte größte gemeinsame Teiler für die Zahlen $a$ und $b$.

Eigenschaften von GCD und LCM

1. Jedes gemeinsame Vielfache von $a$ und $b$ ist durch K$(a;b)$ teilbar
2. Wenn $a\vdots b$ , dann К$(a;b)=a$

Wenn K$(a;b)=k$ und $m$ eine natürliche Zahl ist, dann ist K$(am;bm)=km$

Wenn $d$ ein gemeinsamer Teiler für $a$ und $b$ ist, dann ist K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Wenn $a\vdots c$ und $b\vdots c$ , dann ist $\frac(ab)(c)$ das gemeinsame Vielfache von $a$ und $b$

Für alle natürlichen Zahlen $a$ und $b$ gilt die Gleichheit

$D(a;b)\cdot Š(a;b)=ab$

Jeder gemeinsame Teiler der Zahlen $a$ und $b$ ist ein Teiler der Zahl $D(a;b)$