GCD und LCM-Verhältnis
Die folgende Beziehung funktioniert nur für zwei (3, 12) zahlen, es nicht zu produzieren die richtige Antwort, wenn Sie drei zahlen (3,12,10) . Einfach Fragen, wenn ist es mein Verständnis, oder ist es nur für zwei zahlen und, für mich gleiche gilt für Euclid-Algorithmus.
LCM(a, b) = (a x b) /GCD(a,b) or GCD(a,b) = (a x b) /LCM(a, b)
- Bitte ignorieren Sie den letzten Teil der Frage über Euclid-Algorithmus , es scheint zu funktionieren mit Rekursion.
- Ich werde die Abstimmung zu schließen, ist diese Frage off-topic, weil es um Mathematik, nicht der Programmierung.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Den analogen Formeln zu
mit drei Variablen einfach nicht gültig, wie dein Beispiel mit (3, 12, 10) zeigt, leicht.
Das Produkt dieser drei zahlen ist 360. Der GCD ist 1. Das LCM 60 ist.
Es ist unsere gemeinsame Natur, um zu versuchen und zu vereinfachen/generalize Dingen durch das finden von mustern. Allerdings, wenn es mir intuitiv zu versuchen, die Idee, durch die Ausweitung auf den Allgemeinen Fall von n Variablen, es funktioniert nicht in diesem Fall. Ich werde versuchen, brechen die Logik hinter der Formel .
Zuerst müssen wir verstehen, wie die Formel von LCM(x,y) * GCD(x,y) = x * y haben könnte. Zu finden LCM oder GCD, einen Weg zu brechen, jede der zahlen in Ihre Primfaktoren.
Let x = 84, y = 30
x = 2*2*3*7 = (2*3)*2*7
y = 2*3*5 = (2*3)*5
Den Teil in der Klammer ist der Allgemeine Teil. So dass wir sagen, ok, 2*3, also 6 sollten in der Lage sein sich zu teilen x und y beide und nennen es den GRÖßTEN gemeinsamen Teiler. Wohlgemerkt, nur 2 oder nur 3 sind auch gemeinsame Teiler von x und y, aber nicht den GRÖßTEN gemeinsamen Teiler.
Finden Sie das kleinste gemeinsame Vielfache nehmen wir den GCD und multiplizieren Sie ihn mit all den zahlen, die hinter sich gelassen. Also unsere LCM ist (2*3)*2*7*5 = 420. Ich bin nicht beschreibt die intuition hinter diesem, wie es einfach ist und auch nicht direkt relevant.
Also, wenn Sie multiplizieren x und y, die Sie erhalten 84*30 = (2*3*2*7)*(2*3*5) = (2*3)*((2*3)*2*7*5) = GCD(x,y)*LCM(x,y) = (2*3)*(2*3)*(2*7*5) = [allgemeiner Teil angehoben, um Strom 2, da es wiederholt sowohl die Anzahl] * [der rest der übrig Faktoren, die in allen zahlen].
Nun zu deiner Frage, wenn du eine weitere variable z = 18 = (2*3)*3, GCD alle 3 zahlen ist der gemeinsame Teil (2*3), d.h., 6 und LCM ist (2*3)*2*7*5*3, was auch immer das ist.
Nun x*y*z = (2*3)*(2*3)*(2*3)*(2*7*5*3) = [allgemeiner Teil angehoben, um power 3, da es sich in allen 3 zahlen] * [der rest der übrig Faktoren, die in allen zahlen]. Aber wenn Sie mehrere GCD und LCM erhalten Sie nur (2*3)*((2*3)*2*7*5*3) = (2*3)*(2*3)*(2*7*5*3), d.h. der Allgemeine Teil wird in Betracht gezogen, nur zweimal statt dreimal.
Jedoch, es kann auch der Fall sein, wenn einige der Faktoren zwischen ein paar zahlen (nicht alle, also nicht in GCD) sind Häufig. Im Allgemeinen Fall von n Variablen, GDD(x[1],x[2],...x[n]) = c[1]c[2]..c[k], wo jeder von c[i] 1<=i<=k existiert, einmal in all den zahlen. LCM((x[1],x[2],...x[n]) = GCD(x[1],x[2],...x[n]) * ((h(p[1]) * h(p[2]) * ... h(p[l])), wobei jedes p[j], 1<=j<=l eine Primzahl in der Liste der Links über Faktoren nicht Teil von GCD und h(p[i]) ist die höchste Potenz von p[i] in keiner von Ihnen.
Nun, wenn wir multiplizieren LCM und GCD n zahlen, abgesehen von verlieren sich auf die Faktoren, die den GCD auf etwas mehr als zweimal haben wir auch Locker auf die Faktoren, die teilweise Gemeinsamkeiten zwischen einigen der zahlen und finden nur das Ergebnis der höchsten Kräfte, die vorhanden sind, multipliziert, um den GCD.