Wie viele Lösungen gibt es bei ggT und LCM von n positiven ganzen Zahlen?

Frage: Angenommen, Sie wissen es G := gcd (größter gemeinsamer Teiler) und L := lcm (kleinstes gemeinsames Vielfaches) von N positive ganze Zahlen; Wie viele Lösungsmengen gibt es?

Im Fall von N = 2 , findet man das für die k verschiedene Primzahlen teilen L / G , es gibt insgesamt 2 k − 1 einzigartige Lösungen.

Ich schreibe gerne einen Beweis dafür N = 2 falls gewünscht, aber meine Frage hier betrifft die allgemeinere Version. Der N = 3 Der Fall hat sich bei meinen Untersuchungen bereits als heikel erwiesen, daher würde ich mich freuen, wenn kleinere Fälle ausgearbeitet würden, selbst wenn die Antwortenden sich über die vollständige Verallgemeinerung nicht sicher sind.

Alternativ: Wenn es bereits einen Hinweis auf dieses Problem und seine Lösung gibt, dann wäre auch ein Hinweis auf eine solche Information sehr willkommen!

@Yorch Ihr Kommentar verlinkt nur auf die Frage in dem Fall, in dem N = 2 ; Für mich war dieser Fall kein Problem! Ich frage speziell nach dem allgemeinen Fall : Wo Sie positive ganze Zahlen haben { A 1 , … , A N } .
verlangen Sie, dass die N positive ganze Zahlen verschieden sein? Versuchen Sie, die Multisets zu zählen? Ich glaube, das ist die einzige Version, die ich nicht lösen konnte.
@Yorch Keine Anforderung, dass die ganzen Zahlen unterschiedlich sind und / aber (idealerweise!) unterschiedliche Lösungen zählen. Wenn Sie der Meinung sind, dass Sie mit einer modifizierten Version Traktion erzielen können (dh zusätzliche Einschränkungen auferlegen), würde ich mich trotzdem freuen, zu sehen, was Sie sich einfallen lassen.

Antworten (2)

Wenn Sie daran interessiert sind, Tupel zu zählen ( A 1 , A 2 , … , A N ) so dass gcd ( A 1 , … , A N ) = G Und lcm ⁡ ( A 1 , … , A N ) = L dann können wir es wie folgt machen.

Wenn L / G = ∏ ich = 1 S P ich X ich dann jeweils A ich muss die Form haben G ∏ J = 1 S P ich j ich , J mit 0 ≤ j ich , J ≤ X ich .

Also für jede Primzahl P ich Wir verlangen, dass die Funktion von { 1 , … , N } Zu N das sendet J Zu j ich , J eine Funktion sein, die trifft 0 Und X ich .

Die Anzahl solcher Funktionen ist einfach durch Inklusion-Exklusion z X ich ≥ 1 , es ist ( X ich + 1 ) N − 2 ( X ich ) N + ( X ich − 1 ) N .

Daraus folgt die Gesamtzahl der Tupel ∏ ich = 1 S ( ( X ich + 1 ) N − 2 X ich N + ( X ich − 1 ) N ) .

Zählen von Tupeln wie in, mit Wiederholung, richtig? Z.B ( 1 , 2 ) Und ( 2 , 1 ) würde jeder in Ihrer Berechnung gezählt werden? Wenn ja, ist es nicht der Fall, dass Sie (unter Verwendung Ihrer Notation) die zuweisen könnten S verschiedene Primzahlen (zu ihren verschiedenen Potenzen) als Teiler eines der N Ganzzahlen oder eine Teilmenge davon (z. B. to { A 1 , A 3 , A 7 } )? Es gibt 2 N Teilmengen von { A 1 , … , A N } , aber wir schließen den vollständigen Satz aus (dies ist die gcd ) sowie die leere Menge für insgesamt 2 N − 2 Teilmengen. Vorgenanntes zuweisen S Primzahlen können jetzt in in ausgeführt werden S 2 N − 2 Wege. Oder habe ich das falsch verstanden?
Ja, so sieht es aus, wenn keine Primzahl mehr als einmal vorkommt L / G , würden Sie bekommen ( 2 N − 2 ) S @BenjaminDickman, wenn Sie eine Primzahl mit einem Exponenten größer als haben 1 Teilen L / G es wird komplexer.
Ich bin mir nicht sicher, ob ich deiner Argumentation voll folgen kann. Glaubst du, du könntest ein konkretes Beispiel (in deiner Antwort) dafür erarbeiten? N = 3 oder N = 4 ? Ich bin mir nicht ganz sicher, wie ein Prime, das mehr als einmal erscheint, meinen vorherigen Kommentar verändert, und ich sehe auch nicht genau, wie Sie das IEP aufrufen. Wäre super wenn du Zeit hast!
überlegen wir uns G = 1 Und L = 8 Und N = 3 . Hier müssen wir das jeder haben A ich ist einer von 1 , 2 , 4 , 8 , und wir setzen voraus, dass mindestens einer von ihnen dies ist 1 und mindestens einer von ihnen ist 8 , es gibt 4 3 insgesamt Tupel gibt es 3 3 Tupel, die den Wert eins nicht erreichen, gibt es 3 3 die den Wert nicht treffen 8 und da sind 2 3 das trifft auch nicht, also gibt es 4 3 − 2 ( 3 3 ) + 2 3 insgesamt Triples, die funktionieren.
Ah gut! Ich wurde auch auf dieselbe Antwort wie Theorem 2.7 hier hingewiesen: derby.openrepository.com/handle/10545/583372 (ich kann eine Antwort mit diesem Effekt hinzufügen)
Der Fall G , L ist genauso der Fall 1 , L / G

(Hinzufügen dieser Community-Wiki -Antwort, um auf eine relevante Referenz hinzuweisen.) Ich wurde kürzlich auf das folgende Papier hingewiesen, in dem dieses und verwandte Probleme vorgeschlagen und gelöst werden:

Bagdasar, O. (2014.) "Über einige Funktionen, die lcm und gcd von ganzzahligen Tupeln betreffen." Wissenschaftliche Veröffentlichungen der Staatlichen Universität Novi Pazar Reihe A: Angewandte Mathematik, Informatik und Mechanik, 6(2):91-100. PDF (keine Paywall).

Das Ergebnis erscheint als Theorem 2.7 (vgl. auch den Kommentar von Yorch ):

Geben Sie hier die Bildbeschreibung ein

Wie viele Lösungen gibt es bei ggT und LCM von n positiven ganzen Zahlen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v