Zahlenpaare mit kgV?

Hallo, ich wollte mal fragen, ob es eine Möglichkeit gibt alle Zahlenpaare zu finden, die das gleiche kleinste gemeinsame Vielfache haben. Wie zum Beispiel 1000.

Answer 1

[mihisu]

[Ich bleibe mal im Bereich der natürlichen Zahlen. Man könnte auch in den Bereich der ganzen Zahlen gehen, dann kämen noch entsprechende negative Zahlen hinzu.]

Ja.

=============

Beispielsweise so:

Suche alle Zahlen die 1000 als Vielfaches haben. D.h. du suchst die Teiler von 1000. Das sind ...

1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000

Auf die Teiler kommt man beispielsweise, indem man die Primfaktor Zerlegung

$1000=2^3\cdot5^3$

betrachtet. Die Teiler von 1000 sind dementsprechend die Zahlen

$2^s\cdot5^t$

mit s ∈ {0, 1, 2, 3} und t ∈ {0, 1, 2, 3}.

Nun nimmst du dir jeweil einen Teiler von 1000 als erste Zahl a eines entsprechenden Zahlenpaares (a, b).

Wenn man nun eine Zahl beispielsweise a = 40 betrachtet, so braucht man noch eine Zahl b, so dass kgV(a, b) = 1000 ist.

b muss auch wieder ein Teiler von 1000 sein. Aber nicht irgendein Teiler von 1000, sondern so, dass b die Zahl a „passend ergänzt“. Bei a = 40 = 2³ ⋅ 5 hat man beim Primfaktor 2 schon den Exponenten 3, wie auch in der Primfaktorzerlegung 2³ ⋅ 5³ von 1000. Allerdings hat man bei 5 nur Exponent 1, statt Exponent 3. Dementsprechend muss b also 5³ in der Primfaktorzerlegung haben, damit man bei kgV(a, b) auf 2³ ⋅ 5³ kommt. b muss also einerseits ein Vielfaches von 5³ und andererseits ein Teiler von 1000 = 2³ ⋅ 5³ sein. Dementsprechend hat man für b die Möglichkeiten

$2^k\cdot5^3$

mit k ∈ {0, 1, 2, 3}.

============

Diese Überlegungen führen dann darauf, dass man zu 1000 = 2³ ⋅ 5³ zunächst einen Teiler

$a=2^s\cdot5^t$

mit s ∈ {0, 1, 2, 3} und t ∈ {0, 1, 2, 3} wählen kann, und dann jeweils

$b=2^k\cdot5^m$

mit k ∈ {0, 1, 2, 3} und m ∈ {0, 1, 2, 3} wählen kann, wobei allerdings ...

... k = 3 sein muss, wenn s < 3 ist.
... m = 3 sein muss, wenn t < 3 ist.

Dementsprechend erhält man die folgenden Zahlenpaare (a, b) mit kgV(a, b) = 1000 ...

(2^0 * 5^0, 2^3 * 5^3) = (   1, 1000)
(2^0 * 5^1, 2^3 * 5^3) = (   5, 1000)
(2^0 * 5^2, 2^3 * 5^3) = (  25, 1000)
(2^0 * 5^3, 2^3 * 5^0) = ( 125,    8)
(2^0 * 5^3, 2^3 * 5^1) = ( 125,   40)
(2^0 * 5^3, 2^3 * 5^2) = ( 125,  200)
(2^0 * 5^3, 2^3 * 5^3) = ( 125, 1000)
(2^1 * 5^0, 2^3 * 5^3) = (   2, 1000)
(2^1 * 5^1, 2^3 * 5^3) = (  10, 1000)
(2^1 * 5^2, 2^3 * 5^3) = (  50, 1000)
(2^1 * 5^3, 2^3 * 5^0) = ( 250,    8)
(2^1 * 5^3, 2^3 * 5^1) = ( 250,   40)
(2^1 * 5^3, 2^3 * 5^2) = ( 250,  200)
(2^1 * 5^3, 2^3 * 5^3) = ( 250, 1000)
(2^2 * 5^0, 2^3 * 5^3) = (   4, 1000)
(2^2 * 5^1, 2^3 * 5^3) = (  20, 1000)
(2^2 * 5^2, 2^3 * 5^3) = ( 100, 1000)
(2^2 * 5^3, 2^3 * 5^0) = ( 500,    8)
(2^2 * 5^3, 2^3 * 5^1) = ( 500,   40)
(2^2 * 5^3, 2^3 * 5^2) = ( 500,  200)
(2^2 * 5^3, 2^3 * 5^3) = ( 500, 1000)
(2^3 * 5^0, 2^0 * 5^3) = (   8,  125)
(2^3 * 5^0, 2^1 * 5^3) = (   8,  250)
(2^3 * 5^0, 2^2 * 5^3) = (   8,  500)
(2^3 * 5^0, 2^3 * 5^3) = (   8, 1000)
(2^3 * 5^1, 2^0 * 5^3) = (  40,  125)
(2^3 * 5^1, 2^1 * 5^3) = (  40,  250)
(2^3 * 5^1, 2^2 * 5^3) = (  40,  500)
(2^3 * 5^1, 2^3 * 5^3) = (  40, 1000)
(2^3 * 5^2, 2^0 * 5^3) = ( 200,  125)
(2^3 * 5^2, 2^1 * 5^3) = ( 200,  250)
(2^3 * 5^2, 2^2 * 5^3) = ( 200,  500)
(2^3 * 5^2, 2^3 * 5^3) = ( 200, 1000)
(2^3 * 5^3, 2^0 * 5^0) = (1000,    1)
(2^3 * 5^3, 2^0 * 5^1) = (1000,    5)
(2^3 * 5^3, 2^0 * 5^2) = (1000,   25)
(2^3 * 5^3, 2^0 * 5^3) = (1000,  125)
(2^3 * 5^3, 2^1 * 5^0) = (1000,    2)
(2^3 * 5^3, 2^1 * 5^1) = (1000,   10)
(2^3 * 5^3, 2^1 * 5^2) = (1000,   50)
(2^3 * 5^3, 2^1 * 5^3) = (1000,  250)
(2^3 * 5^3, 2^2 * 5^0) = (1000,    4)
(2^3 * 5^3, 2^2 * 5^1) = (1000,   20)
(2^3 * 5^3, 2^2 * 5^2) = (1000,  100)
(2^3 * 5^3, 2^2 * 5^3) = (1000,  500)
(2^3 * 5^3, 2^3 * 5^0) = (1000,    8)
(2^3 * 5^3, 2^3 * 5^1) = (1000,   40)
(2^3 * 5^3, 2^3 * 5^2) = (1000,  200)
(2^3 * 5^3, 2^3 * 5^3) = (1000, 1000)

Answer 2

[ShimaG]

Ich würde das so angehen:

Das kleinste gemeinsame Vielfache von a und b ist, wenn man natürliche Zahlen m und n findet, teilerfremd, so daß a * m = b * n ist.

Die Frage ist nun, wenn du ein KGV k vorgibst, wie viele solcher Tupel (a,b,m,n) es gibt, so daß

1. Es gibt a > 0, m > 0, so daß a * m = k
2. Es gibt b > 0, n > 0, so daß b * n = k
3. m und n sind teilerfremd

Wenn du m und n konstruiert hast, ergeben sind a und b, da k fest vorgegeben ist.

Offenbar sind m und n Teiler von k.

Praktisch würde ich das dann so machen:

1. Bestimme T(k), die Menge alle Teiler von k; das sind Kandidaten für m und n.
2. Für das Paar (m_i, n_i), m_i aus T(k), n_i aus T(k), bestimme, ob es einen gemeinsamen Teiler > 1 gibt. Wenn ja, ist Bedingung 3 verletzt, und das Paar wird ausgeschlossen
3. Da kgV(a,b) = kgV(b,a), würde ich (m_i, n_i) auch ausschließen, wenn m_i > n_i ist.
4. Für die verbleibenden Paare kannst du dann a_i und b_i ausrechnen per a_i = k / m_i, b_i = k/n_i.

Zu deinem Beispiel:

k = 1000

Damit

T(1000) = {1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000}

• Für m = 1 muß n = 1 folgen, da ansonsten (4) oben verletzt ist
• Für m = 2 gibt es nur die Möglichkeit n = 1
• Für m = 4 gibt es ebenfalls nur die Möglichkeit n = 1
• Für m = 5 folgt n\in{1, 2, 4}
• Für m = 8 folgt n=1 oder n=5, da 2, 4 gemeinsame Teiler mit 8 haben
• Für m = 10 folgt n=1, da 2, 4, 5, 8 alle gemeinsame Teiler mit 10 haben.
• Für m\in{20, 40, 50, 100, 200, 250, 500, 1000} folgt n=1, da alle anderen Elemente aus T(1000) einen gemeinsamen Teiler mit m haben.
• Für m = 25 kann n\in{1,2,4,8} sein.
• Für m = 125 kann n\in{1,2,4,8} sein

Aus den so definierten 25 Paaren für (m,n) kannst du dann (a,b) ausrechnen.

Beispiel: m = 8, n = 5 => a = 1000/8=125, b = 1000/5=200

Woher ich das weiß: Hobby

Comments

[mihisu]

Die Antwort ist gut. Auch wenn sich an der ein oder anderen Stelle kleine Schreibfehler bzw. Unstimmigkeiten eingeschlichen haben, über die ich gestolpert bin. [Beispielsweise schreibst du an einer Stelle dass du Paare (m_i, n_i) mit m_i > n_i ausschließen möchtest, schließt dann aber bei deinem Beispiel umgekehrt stattdessen die Paare (m, n) mit m < n aus.]

============

Über die Kofaktoren m, n zu gehen, die dann teilerfremd sein müssen, ist eine schöne Idee. Da kann man auch recht leicht ein Programm dazu schreiben, welches das abarbeitet. Mit Python beispielsweise:

def ggT(a, b):
    while b:
        a, b = b, a % b
    return(a)
k = 1000
Teiler = [t for t in range(1, k+1) if k % t == 0]
for m in Teiler:
    for n in Teiler:
        if ggT(m, n) == 1:
            print([k//m, k//n])

Ausgabe:

[1000, 1000]
[1000, 500]
[1000, 250]
[1000, 200]
[1000, 125]
[1000, 100]
[1000, 50]
[1000, 40]
[1000, 25]
[1000, 20]
[1000, 10]
[1000, 8]
[1000, 5]
[1000, 4]
[1000, 2]
[1000, 1]
[500, 1000]
[500, 200]
[500, 40]
[500, 8]
[250, 1000]
[250, 200]
[250, 40]
[250, 8]
[200, 1000]
[200, 500]
[200, 250]
[200, 125]
[125, 1000]
[125, 200]
[125, 40]
[125, 8]
[100, 1000]
[50, 1000]
[40, 1000]
[40, 500]
[40, 250]
[40, 125]
[25, 1000]
[20, 1000]
[10, 1000]
[8, 1000]
[8, 500]
[8, 250]
[8, 125]
[5, 1000]
[4, 1000]
[2, 1000]
[1, 1000]

Wobei man auch k einfach durch andere Zahlen ersetzen kann, wenn man nicht 1000 als kgV haben möchte, sondern eine andere Zahl.

Mit dem genannten Programm erhält man nicht nur, wie von dir vorgeschlagen, die Paare (a, b) mit a ≤ b bzw. m ≥ n, um den Rechenaufwand/Schreibaufwand zu reduzieren. [Da man dann ja auch automatisch schon weiß, dass dann auch (b, a) ein entsprechendes Paar ist.] Wenn man nur die Paare mit a ≤ b haben möchte, könnte man beispielsweise das Python-Programm so abändern:

def ggT(a, b):
    while b:
        a, b = b, a % b
    return(a)
k = 1000
Teiler = [t for t in range(1, k+1) if k % t == 0]
for m in Teiler:
    for n in Teiler:
        if m >= n and ggT(m, n) == 1:
            print([k//m, k//n])

Ausgabe:

[1000, 1000]
[500, 1000]
[250, 1000]
[200, 1000]
[200, 500]
[200, 250]
[125, 1000]
[125, 200]
[100, 1000]
[50, 1000]
[40, 1000]
[40, 500]
[40, 250]
[40, 125]
[25, 1000]
[20, 1000]
[10, 1000]
[8, 1000]
[8, 500]
[8, 250]
[8, 125]
[5, 1000]
[4, 1000]
[2, 1000]
[1, 1000]

[Raytex27]

@mihisu

Kann ich das Programm auch irgenwie selbst verwendern?

[mihisu]

@Raytex27

Klar. Installier einfach Python, falls du es nicht am PC hast.

Oder wenn du nichts installieren möchtest, kannst du das auch online ausführen lassen. Beispielsweise hier: https://repl.it/repls/NearHandsomeBases

[Raytex27]

@mihisu

Danke!

Answer 3

[lks72]

Es geht um die Primfaktorzerlegung von 1000, also 1000 = 2^3 * 5^3.

Das kgV einer Zahl ist die Zahl, die die maximale Potenz jedes vorkommenden Primfaktors enthält. Also sind es alle Zahlenpaare a und b, in denen in a oder b (oder beidem) die Primfaktoren 2 und 5 jeweils 3 mal vorkommen.

Beispiel 1: 2^1 * 5^3 und 2^3 * 5^1, also 250 und 40.

Beispiel 2: 2^3 * 5^0 und 2^2 * 5^3, also 8 und 500.

u.s.w.

Woher ich das weiß: Studium / Ausbildung

Answer 4

[gfntom]

ja, dafür gibt es Methoden. Stichwort: Primfaktoren.