Voraussetzungen

• Primzahlen
• Der absolute Wert

Bestimmung

GCD

GCD steht für größter gemeinsamer Teiler. Die Definition von GCD ist daher wie folgt. Seien a und b zwei ganze Zahlen. Der ggT von a und b ist die größte Zahl, die sowohl a als auch b teilt. Wir bezeichnen es mit a ∧ b oder ggT(a,b).
Wenn ggT(a,b) = 1 ist, sagen wir, dass a und b teilerfremd sind.

Beispiel :
Nimm 12 und 18. ggT(12,18) = 6. 6 ist der größte gemeinsame Teiler von 12 und 18.

LCM

PPCM steht für am wenigsten üblich mehrere. Die Definition von PPCM ist daher wie folgt. Seien a und b zwei ganze Zahlen. Das LCM von a und b ist die kleinste ganze Zahl n > 0, sodass a | b und w | nicht. Sie wird bezeichnet mit a ∨ b oder lcm(a,b)

Beispiel : Wir nehmen immer noch 12 und 18. lcm(12,18) = 36. Einfache Begründung: Das erste Vielfache von 18 ist 18. 12 teilt 18 nicht. Wir werden daher nach dem folgenden Vielfachen suchen, 36. Da 12 auch 36 teilt , 36 ist in der Tat die PPCM zwischen 12 und 18.

Propriétés

Es gibt verschiedene Eigenschaften rund um GCDs:

\begin{array}{l}\forall a,b \in \mathbb{Z}, \forall c \in \mathbb{Z}, \text{pgcd}\left(a,b\right) = \text{ gcd}\left(b,a\right)\\ \forall a,b \in \mathbb{Z}, \text{pgcd}\left(a,b\right)= \text{pgcd}\left(a -bc,b\right)\\ \forall a,b,c \in \Z, \text{pgcd}\left(ca,cb\right) = \left|c\right|\text{pgcd}(a ,b)\\ \für alle a,b,c \in \mathbb{Z},\text{pgcd}\left(a,b,c\right) = \text{pgcd}\left(a,pgcd \left (b,c\right)\right) = ggT \left(\text{ggT}\left(a,b\right),c\right)\\ \forall a,b \in \Z, \text{ggT }(a,b) = a \Leftrightarrow a |b\ \\ \forall a \in \Z, \text{gcd}(a,0) = a \end{array}

Wir haben ähnliche Eigenschaften rund um das PPCM:

\begin{array}{l}\forall a,b\ \in\mathbb{Z}, \forall c \in\mathbb{Z},\ \text{ppcm}\left(a,b\right) =\ text{ppcm}\left(b,a\right)\\ \forall a,b,c\ \in \Z,\text{ppcm}\left(ca,cb\right) = \left|c\right| \text{ppcm}\left(a,b\right)\\ \forall a,b,c\ \in\mathbb{Z},\text{ppcm}\left(a,b,c\right)=\ text{ppcm}\left(a,\text{ppcm}\left(b,c\right)\right) = \text{ppcm}\left(\text{ppcm}\left(a,b\right), c\right)\\ \forall a,b\in\mathbb{Z},\text{ppcm}(a,b)=a\ \Leftrightarrow\ b|a\end{array}

Und andere, die PGCD und PPCM mischen

\begin{array}{l}\forall a,b\in \mathbb{Z}, \text{pgcd}\left(a,b\right)\ \times \text{ppcm}\left(a,b\ rechts) = \links|ab\rechts| \text{(dies ist zu merken)}\\ \forall a,b,c \in\mathbb{Z}, \text{pgcd}\left(a,\text{ppcm}\left(b,c \ right)\right) =\text{ppcm}(\text{gcd}\left(a,b),\text{gcd}\left(a,c\right)\right)\\ \forall a,b , c\in\mathbb{Z},\\text{ppcm}\left(a,\text{pgcd}\left(a,b\right)\right)=\text{pgcd}\left(\text{ppcm }\left(a,b\right),\text{ppcm}\left(a,c\right)\right)\\ \forall a,b,c \in \Z,\\ \text{gcd} ( \text{ppcm}(a,b),\text{ppcm}(a,c),\text{ppcm}(b,c))=\text{ppcm}(\text{gcd}(a,b ) ,\text{gcd}(a,c),\text{gcd}(b,c))\end{array}

Berechnungsmethoden

Im Allgemeinen berechnen wir zur Berechnung des PPCM zuerst den GCD und wenden die oben gezeigte Formel an:

 \text{ppcm}\left(a,b\right)\ =\ \frac{\left|ab\right|}{\text{gcd}\left(a,b\right)}

Durch die Teiler

Diese Methode ist die grundlegendste, funktioniert aber sehr gut. Wir listen die Teiler jeder Zahl auf und nehmen die größte Gemeinsamkeit in die Liste.

exemples:
1) Lassen Sie uns den GCD von 50 und 45 berechnen.
Liste der Teiler von 50: 1, 2, 5, 10, 25, 50
Liste der Teiler von 45: 1, 3, 5, 9, 15, 45
Der ggT ist daher 5, da er der größte Teiler ist, den diese beiden Zahlen gemeinsam haben.
2) Berechnen Sie den GCD von 210 und 330
Liste der Teiler von 210: 1, 2, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 105, 210
Liste der Teiler von 330: 1, 10, 11, 30, 33, 330
Der GCD beträgt daher 30.

Nach dem Primzahlsatz

Wir zerlegen in Produkte von Primzahlen (siehe Artikel über Primzahlen) die Zahlen, aus denen wir GCD berechnen wollen. Wir nehmen dann den kleinsten Macht allen gemeinsam, um den ggT zu berechnen. Wenn wir die PPCM berechnen wollen, müssen wir dann die jeweils größte gemeinsame Potenz nehmen.

\begin{array}{l}\text{Let } a\in\mathbb{N}, a =\displaystyle \prod_{i=1}^np_i^{\alpha_i}\\\ \text{Let } b \ in\mathbb{N}, b =\displaystyle\prod_{i=1}^np_i^{\beta_i}\\ \text{(mit potentiell }\alpha_i = 0 \text{ oder } \beta_{i}=0 )\end{array}

dann,

\begin{array}{l} \text{pgcd}\left(a,b\right) =\displaystyle \prod_{i=1}^np_i^{\min\left(\alpha_i,\beta_i\right)} \\ \text{ppcm}\left(a,b\right) =\displaystyle \prod_{i=1}^np_i^{\max\left(\alpha_i,\beta_i\right)} \end{array}

Beispiel :
Lassen Sie uns den GCD und den PPCM von 45 und 50 berechnen
45 = 5 x 3² = 5x3² x 2⁰
50 = 5² x 2 = 5² x 3⁰ x 2¹
Der ggT ist also 5 x 3⁰ x 2⁰ = 5
LCM ist 5² x 3² x 2¹ = 450

Nach Euklids Algorithmus

Euklidische Teilung

Seien a und b zwei ganze Zahlen, b > 0. Die euklidische Division von a durch b besteht darin, die eindeutigen q und r so zu finden, dass:

\begin{array}{l}a\=\bq\+\r\\0\\le\r\<\b\end{array}

Bewerbung beim GCD

Wir verwenden die folgende Formel: ggT(a,b) = ggT(a-bq,b) = ggT(b,r)
Hier ist der Euklid-Algorithmus:
Wir machen die euklidische Division von a durch b. Wenn der Rest r₁ nicht Null ist, führen wir die euklidische Division von b durch r durch₁. Erhalten wir einen Rest r₂ ungleich Null, führen wir die euklidische Division von r durch₁ von r₂. Wir erhalten einen Rest r₃. Und wir fahren fort, bis wir null Rest bekommen.
Der ggT ist der letzte Rest ungleich Null.

Beispiel 1
Berechnen Sie durch euklidische Division die ggT von 50 und 45.
50 = 45 x 1 + 5
45 = 5 x 9 + 0
Der letzte Rest ungleich Null ist 5. Das ist also der ggT zwischen 45 und 50.

Beispiel 2
Berechnen Sie den ggT zwischen 210 und 330 durch euklidische Division.
330 = 210 x 1 + 120
210 = 120 x 1 + 90
120 = 90 x 1 + 30
90 = 30 x 3 + 0
Der ggT von 210 und 330 ist also 30.

Beispiel 3
Zeigen Sie, dass n und n + 1 teilerfremd sind, also ggT(n,n+1) = 1
Mit der euklidischen Division ist es ganz einfach:
n+1 = nx1+1
n=1xn+0
Der letzte von Null verschiedene Rest ist daher 1. n und n+1 sind daher teilerfremd

GCD- und PPCM-Rechner

GCD-Rechner

Müssen Sie Ihre Berechnungen überprüfen? Nutzen Sie unsere Berechnen um das richtige Ergebnis zu finden!

LCM-Rechner

Trainings-Einheiten

Übung 1
Berechnen Sie den ggT der folgenden Paare mit dem Euklid-Algorithmus

1. 756 und 306
2. 15489 und 156
3. 154 und 39
4. 168 und 204
5. 788 und 504

Übung 2
Berechnen Sie den ggT der folgenden Paare mit Primfaktorzerlegung

1. 360 und 144
2. 3345 und 600
3. 6209 und 4435
4. 675 und 375
5. 682 und 352

Übung 3
Seien m und n so, dass m + n a ist Primzahl. Zeigen Sie, dass m und n teilerfremd sind.

Übung 4
Bestimmen Sie den ggT zwischen 9n+6 und 2n+1 mit 2 Methoden Ihrer Wahl

Übung 5
Löse die folgenden Gleichungen:

\left\{\begin{matrix}xy\ &=&3456\\ gcd\left(x,y\right)&=&12\end{matrix}\right. 

\left\{\begin{matrix}xy\ &=&864\\ gcd\left(x,y\right)&=&12\end{matrix}\right.

Übung 6
Finde alle positiven ganzen Zahlen a und b, so dass ggT(a,b) = 5 und lcm(a,b) = 306

Übung 7
Finden Sie alle positiven ganzen Zahlen a und b, so dass ggT(a,b) = 7 und a² – ab = 3456

Hier finden Sie unsere neuesten Bac Review-Artikel:

• Die Gesamtwahrscheinlichkeitsformel: Demonstration und Übungen
• Gerade und ungerade Funktionen: Lektionen und korrigierte Übungen
• Satz von Bayes: Aussage, Demonstration und korrigierte Aufgaben
• Die Würfelfunktion: Kurse und korrigierte Übungen
• Die quadratische Funktion: Kurse und korrigierte Aufgaben