Größter gemeinsamer Teiler (ggT) sowie kgV

Question

Aufgaben:

1.  Begründe entweder  verbal oder formal. (ausführlich) , warum folgende Gleichung gilt: a · b = ggT (a, b) · kgV(a,b)

2. Für zwei Zahlen a, b ∈ N gilt ggT (a, b) = 30 und kgV (a, b) = 4200. Bestimme alle möglichen Zahlen a und b für die dies gilt und erkläre dein Vorgehen.  Die Gleichung aus a) darf benutzt werden.

3. Leiten aus  deiner Überlegung aus b) eine allgemeine Regel her, mit deren Hilfe man die Anzahl der Zahlenpaare a und b finden kann, die möglich sind, wenn der ggT und das kgV dieser Zahlen gegeben sind. Begründe deine Regel.

Answer 1

machen wir's mit Mengenlehre:

 \(P_a\) sei die Menge aller Primfaktoren von \(a\); wobei Faktoren doppelt vorkommen dürfe. Doppelte Faktoren werden durchnummeriert. Und \(P_b\) sei dieselbe Menge für \(b\). Weiter sei \(T_{a,b}\) die  Menge aller dieser Faktoren des \(\text{ggT}(a,b)\), sowie \(V_{a,b}\) die Menge der Faktoren im \(\text{kgV}(a,b)\). Dann ist doch offensichtlich$$T_{a,b} = P_a \cap P_b \\ V_{a,b} = P_a \cup P_b$$

Betrachtet man nun beide Mengen \(T_{a,b}\) und \(V_{a.b}\) gemeinsam, dann ist natürlich \(T_{a,b} \subset V_{a,b}\), d.h. jedes Element von \(T_{a,b}\) kommt auch in \(V_{a,b}\) vor, und das sind genau die Faktoren, die in beiden Mengen \(P_a\) und \(P_b\) enthalten sind. Multipliziert man also alle Faktoren der Mengen \(T_{a,b}\) und \(V_{a,b}\), so ist das Ergebnis das selbe als wenn man das Produkt aller Faktoren aus \(P_a\) und \(P_b\) bildet.$$\implies \text{kgV}(a,b) \cdot \text{ggT}(a,b) = a\cdot b$$Beispiel:$$\begin{aligned} a&= 24 \to P_a = \{ 2_1,\, 2_2,\, 2_3, \, 3_1\} \\ b &= 180 \to P_b = \{ 2_1, \, 2_2,\, 3_1,\, 3_2, \, 5\} \\ T_{a,b} &= \{2_1,\, 2_2,\, 3_1\}, \quad \text{ggT} = 2\cdot 2 \cdot 3 = 12 \\ V_{a,b} &= \{2_1, \, 2_2,\, 2_3,\, 3_1,\, 3_2, \, 5 \}, \quad \text{kgV} = 2\cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5= 360 \end{aligned}$$

Zu (2)+(3): Im Prinzip sind zwei Faktoren \(n\) und \(m\) mit \(n,m \in \mathbb{N}\) zu finden, für die folgendes gilt$$\begin{aligned} a &= n \cdot \text{ggT}(a,b) \\ b &= m \cdot \text{ggT}(a,b)  \\ n &\perp m \quad \text{bzw.:} \space \text{ggT}(n,m) = 1\end{aligned} \\ n \cdot m \cdot  \text{ggT}(a,b) =  \text{kgV}(a,b)$$die letzte Gleichung folgt aus \(a\cdot b = \text{ggT}(a,b) \cdot \text{kgV}(a,b)\). Das Produkt von \(n\cdot m\) ist dann $$n \cdot m = 4200 \div 30 = 140 = 2^2 \cdot 5 \cdot 7$$Jetzt noch alle teilerfremden Paare \(n,\,m\) bestimmen, indem man für \(n\) alle Mengen der Potenzmenge von \(\{ 4,\, 5,\, 7\}\) aufstellt und das Produkt der Elemente jeder Menge berechnet. \(m\) ist dann einfach \(m=140 \div n\).$$\begin{array}{rr|rr}n& m& a& b\\ \hline1& 140& 30& 4200\\ 4& 35& 120& 1050\\ 5& 28& 150& 840\\ 7& 20& 210& 600\\ 20& 7& 600& 210\\ 35& 4& 1050& 120\\ 28& 5& 840& 150\\ 140& 1& 4200& 30\end{array}$$und jedes Paar \(a,\,b\) kommt natürlich doppelt vor.

Comments

Wie bist du analog von n,m zu a,b gelangt ?

---

ok, vergiss es habe es jetzt verstanden. Nur zu 3, welcheRegel würdest du daraus herleiten ?

---

Nur zu 3, welcheRegel würdest du daraus herleiten ?

Aih .. da hatte ich gedacht, Du schaffst das nach meiner Vorlage alleine ;-)

Die Anzahl der Paare \(n_P\) ist die Hälfte der Mächtigkeit der Potenzmenge der Menge aller Primfaktoren von $$n \cdot m = \frac{\text{kgV}}{\text{ggT}}$$Die Menge \(\mathbb{P}\) der Primfaktoren ist in obigem Beispiel$$\frac{\text{kgV}}{\text{ggT}} = \frac{4200}{30} = 140 \implies \mathbb{P} = \{2,5,7\} \implies |\mathbb{P}| = 3$$die \(2\) zählt hier nur einmal. Es spielt keine Rolle wie oft ein Primfaktor vorkommt. Und die Mächtigkeit der Potenzmenge \(\mathcal{P}\) der Menge \(\mathbb{P}\) ist $$|\mathcal{P}| = 2^{|\mathbb{P}|}$$ (siehe Potenzmenge/Kardinalität) Somit ist $$n_P = \frac 12 |\mathcal{P}| = \frac 12 \cdot 2^{|\mathbb{P}|} = 2^{|\mathbb{P}|-1}$$In obigem Beispiel wäre das \(n_P= 2^{3-1}=4\). Nämlich die Paare \((30,4200)\), \((120,1050)\), \((150,840)\) und \((210,600)\).

Answer 2

2.  Für zwei Zahlen a, b ∈ N gilt ggT (a, b) = 30 und kgV (a, b) = 4200. Bestimme alle möglichen Zahlen a und b für die dies gilt.

4200 ist durch 30 teilbar. Also gilt dies insbesondere für a=30 und b=4200.Weitere Möglichkeiten ergeben sich nach Faktorenzerlegung von a und b. Im ggT (a, b) müssen alle keinsten Potenzen aus den Primfaktorenzerlegungen vorkommen und im kgV (a, b) müssen alle gößten Potenzen aus den Primfaktorenzerlegungen vorkommen