kgV(d,e)=24

05.09.2016, 17:30	Bastimus Soprano	Auf diesen Beitrag antworten »
kgV(d,e)=24 Hallo, möchte ich hier "d,e" bestimmen, ist das ganze etwas aufwendig: kgV(d,e)=24 Ich habe es bei unterschiedlichen Zahlen versucht, und finde zwar (so denke ich) alle kombinatorischen Möglichkeiten, finde aber keine Gesetzmäßigkeit. Kennt hier jemand einen formalen Ausdruck, mit dem man die Anzahl der Möglichkeiten für "d,e" für jede beliebige Zahl schnell herausfinden kann? Könnt ihr helfen?
05.09.2016, 17:47	HAL 9000	Auf diesen Beitrag antworten »
Basierend auf der Primfaktorzerlegung der beteiligten Zahlen enthält der kgV dieselben Primfaktoren, und zwar jeden mit einem Exponenten, der dem Maximum der Exponenten in den Ausgangszahlen entspricht. Daraus folgt $\begin{align} \operatorname{kgV}\left(2^r\cdot 3^s,2^t\cdot 3^u\right) = 2^{\max(r,t)}\cdot 3^{\max(s,u)} \end{align}$ . Hier nun wegen $\begin{align} 24 = 2^3\cdot 3^1 \end{align}$ fordern wir $\begin{align} \max(r,t)=3 \end{align}$ und $\begin{align} \max(s,u)=1 \end{align}$ . EDIT: Achso, die Anzahl der Paare (d,e) - die ist hier $\begin{align} (2\cdot 3+1)\cdot (2\cdot 1+1) = 21 \end{align}$ .
05.09.2016, 18:16	Bastimus Soprano	Auf diesen Beitrag antworten »
Vielen Dank! Auf 21 bin ich nämlich gekommen. Für das Verständnis von (2x3+1)(2x1+1): Es ist nun jeweils die 2 als erster Faktor enthalten, weil es 2 Primfaktoren sind und der jeweils zweite Faktor entspricht dem jeweiligen Exponenten? Die Addition um 1 ist zu tätigen, damit der Exponent Null berücksichtigt wird?
05.09.2016, 19:55	HAL 9000	Auf diesen Beitrag antworten »
Nein, die 2 ist nicht die Anzahl der Primfaktoren, die 2 steht generell drin. Ist die Primfaktorzerlegung des gewünschten kgV gleich $\begin{align} p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot \ldots \cdot p_m^{\alpha_m} \end{align}$ , so ist die Anzahl solcher Paare $\begin{align} (d,e) \end{align}$ gleich $\begin{align} (2\alpha_1+1)\cdot (2\alpha_2+1)\cdot \ldots\cdot (2\alpha_m+1)\qquad () \end{align}$ . Begründung: Primfaktor $\begin{align} p_k \end{align}$ kann in $\begin{align} (d,e) \end{align}$ in folgenden Kombinationen vertreten sein: $\begin{align} \left(1,p_k^{\alpha_k}\right), \left(p_k,p_k^{\alpha_k}\right), \left(p_k^2,p_k^{\alpha_k}\right),\ldots, \left( p_k^{\alpha_k-1},p_k^{\alpha_k}\right), \left( p_k^{\alpha_k},p_k^{\alpha_k}\right) \end{align}$ Das sind $\begin{align} (\alpha_k+1) \end{align}$ Kombinationen, dazu kommen noch $\begin{align} \left(p_k^{\alpha_k},1\right), \left(p_k^{\alpha_k},p_k\right), \left(p_k^{\alpha_k},p_k^2\right),\ldots, \left( p_k^{\alpha_k},p_k^{\alpha_k-1}\right) \end{align}$ , das sind nochmal $\begin{align} \alpha_k \end{align}$ Kombínationen, die "letzte" $\begin{align} \left( p_k^{\alpha_k},p_k^{\alpha_k}\right) \end{align}$ dürfen wir natürlich nicht doppelt zählen. Das kann man nun für jeden der Primfaktoren machen, und das völlig getrennt voneinander - so ergibt sich über k=1..m das Produkt der Einzelanzahlen (). EDIT: Übrigens kann man das auch auf mehr als zwei Zahlen "aufbohren": Die Anzahl der $\begin{align} r \end{align}$ -Tupel $\begin{align} (d_1,d_2,\ldots,d_r) \end{align}$ positiver ganzer Zahlen mit $\begin{align} \operatorname{kgV}(d_1,d_2,\ldots,d_r) = n \end{align}$ für fest vorgegebenes $\begin{align} n = \prod_{k=1}^m p_k^{\alpha_k} \end{align}$ ist gleich $\begin{align} \prod_{k=1}^m \left((\alpha_k+1)^r-\alpha_k^r\right) \end{align}$ .

1

Verwandte Themen