"Rückrechnung" beim ggt und kgv

Neue Frage »

Ploki Auf diesen Beitrag antworten »
"Rückrechnung" beim ggt und kgv
Hallo!

Ich habe den ggT(m,n) und das kgV(m,n) gegeben. Gibt es einen Algorithmus alle Zahlen zu bestimmen?

lg Ploki
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

alle möglichen Zahlenpaare m,n kann man natürlich identifizieren.
Allerdings gibt es unter Umständen mehrere m,n z.B. (2,3) und (1,6) oder (6,36) und (12,18)
Ploki Auf diesen Beitrag antworten »

Danke für deine Antwort. Angenommen, ggT(m,n) = 18 und kgV(m,n) = 720. Wie muss ich nun vorgehen um alle m,n zu finden, die diese Bedingung erfüllen?
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Wie muss ich nun vorgehen um alle m,n zu finden, die diese Bedingung erfüllen?

Es wird dich keiner zwingen genau einen Weg zu gehen.
Der naheliegendste ist wohl die hoffentlich wohlbekannten Charakterisierungen:
Ist
so ist
HAL 9000 Auf diesen Beitrag antworten »

Folgende Äquivalenz dürfte in dem Zusammenhang hilfreich sein:



Oder in Worten: Einer der beiden Werte ist das Minimum, der andere dann das Maximum.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von Ploki
Danke für deine Antwort. Angenommen, ggT(m,n) = 18 und kgV(m,n) = 720. Wie muss ich nun vorgehen um alle m,n zu finden, die diese Bedingung erfüllen?


Es gilt ja die Beziehung

Jetzt gilt es nur noch alle Zerlegungen des Produktes in zwei Faktoren zu finden, wozu man die Primfaktorzerlegung von benötigt.
 
 
HAL 9000 Auf diesen Beitrag antworten »

Eine kleine, aber wichtige Ergänzung:

Zitat:
Original von RavenOnJ (ergänzt)
Jetzt gilt es nur noch alle Zerlegungen des Produktes in zwei teilerfremde Faktoren zu finden, wozu man die Primfaktorzerlegung von benötigt.
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Eine kleine, aber wichtige Ergänzung:

Zitat:
Original von RavenOnJ (ergänzt)
Jetzt gilt es nur noch alle Zerlegungen des Produktes in zwei teilerfremde Faktoren zu finden, wozu man die Primfaktorzerlegung von benötigt.


Freude klar, da ggT(a,b) = 1 sein muss.

Edit: Sei k die Zahl der Primfaktoren in dem Produkt ab. Dann gibt es Möglichkeiten der Zerlegung. Dies ist die Zahl aller Möglichkeiten, k Kugeln auf 2 Kisten zu verteilen.
Ploki Auf diesen Beitrag antworten »

Danke Leute! Damit komm ich bestimmt weiter =)

lg Ploki
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von RavenOnJ
Sei k die Zahl der Primfaktoren in dem Produkt ab. Dann gibt es Möglichkeiten der Zerlegung. Dies ist die Zahl aller Möglichkeiten, k Kugeln auf 2 Kisten zu verteilen.

Wenn man im Fall allerdings und als verschiedene Lösungen ansieht - was sie etwa bei einer Frage nach der Anzahl der Lösungspaare auch sind - dann würde die Antwort lauten. Kommt also auf den genauen Wortlaut der Fragestellung an. Augenzwinkern
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zitat:
Original von RavenOnJ
Sei k die Zahl der Primfaktoren in dem Produkt ab. Dann gibt es Möglichkeiten der Zerlegung. Dies ist die Zahl aller Möglichkeiten, k Kugeln auf 2 Kisten zu verteilen.

Wenn man im Fall allerdings und als verschiedene Lösungen ansieht - was sie etwa bei einer Frage nach der Anzahl der Lösungspaare auch sind - dann würde die Antwort lauten. Kommt also auf den genauen Wortlaut der Fragestellung an. Augenzwinkern


Deswegen hatte ich auch zuerst geschrieben. Aber die gewöhnliche Frage ist wohl die nach der Zahl aller Möglichkeiten für zwei Zahlen diese Beziehungen zu erfüllen. Deswegen . Whatever...
Ploki Auf diesen Beitrag antworten »

Ich glaube gemeint sind hier 2^(k-1) Möglichkeiten, da ja der ggT kommutativ ist. Is aber ziemlich egal. Es steht zumindest nicht explizit da.

Mein Rechenweg war nun folgender:

,





Damit gibt es nur 2 Möglichkeiten.

,

,

,
,

Stimmt ihr mir zu? smile
HAL 9000 Auf diesen Beitrag antworten »

Stimmt. Freude
Ploki Auf diesen Beitrag antworten »

Danke fürs kontrollieren Augenzwinkern
Tester007 Auf diesen Beitrag antworten »

Wie kann man die von RavenOnJ angegebene Beziehung argumentieren?
Es wird was damit zu tun haben, dass ggT*kgV gleich dem Produkt von m,n sind. Ich komm momentan aber nicht drauf...
RavenOnJ Auf diesen Beitrag antworten »

Zitat:
Original von Tester007
Wie kann man die von RavenOnJ angegebene Beziehung argumentieren?
Es wird was damit zu tun haben, dass ggT*kgV gleich dem Produkt von m,n sind. Ich komm momentan aber nicht drauf...


Genau, denn:


Mit

und


folgt nun


Darüberhinaus solte einem noch klar sein, dass und teilerfremd sind, also . Folgt aus der Defintion von .
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »