Least Common Multiple

Author

Eric W. Weisstein
October 19, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/LeastCommonMultiple.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/LeastCommonMultiple.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Identities

gcd(a,b) lcm(a,b)==(Abs[a b])

FullSimplify[GCD[a,b]LCM[a,b],(a|b)∈Integers]

FullSimplify[GCD[a,b]LCM[a,b],(a|b)∈Rationals]

Table[GCD[a,b]LCM[a,b]-Abs[a b]/.{a->RandomInteger[{-10,10}]/RandomInteger[{1,10}],b->RandomInteger[{-10,10}]/RandomInteger[{1,10}]},{1000}]//Union

Table[Abs[GCD[a,b]LCM[a,b]]-Abs[a b]/.{a->RandomInteger[{-10,10}]+I RandomInteger[{-10,10}],b->RandomInteger[{-10,10}]+I RandomInteger[{-10,10}]},{1000}]//Union

lcm(a,a)==(Abs[a])

LCM[a,a]//FunctionExpand

FullSimplify[LCM[a,a],a∈Integers]

FullSimplify[LCM[a,a],a∈Rationals]

Table[Abs[LCM[a,a]]-Abs[a]/.{a->RandomInteger[{-10,10}]+I RandomInteger[{-10,10}],b->RandomInteger[{-10,10}]+I RandomInteger[{-10,10}]},{1000}]//Union

lcm(a,b)==lcm(b,a)

LCM[a,b]-LCM[b,a]

LCM[b,a]

lcm(lcm(a,b),c)==lcm(a,b,c)

LCM[LCM[a,b],c]

lcm(a,lcm(b,c))==lcm(a,b,c)

LCM[a,LCM[b,c]]

lcm(a m,b m,c m)==(Abs[m]) lcm(a,b,c)

FullSimplify[LCM[m a,m b,m c],(m|a|b|c)∈Integers]

ByteCount/@{LCM[a m,b m,c m],Abs[m] LCM[a,b,c]}

Table[LCM[m a,m b,m c]-Abs[m] LCM[a,b,c]/.{m->RandomInteger[{-10,10}],a->RandomInteger[{-10,10}],b->RandomInteger[{-10,10}],c->RandomInteger[{-10,10}]},{1000}]//Union

Table[LCM[m a,m b,m c]-Abs[m] LCM[a,b,c]/.{m->RandomInteger[{-10,10}]/RandomInteger[{1,10}],a->RandomInteger[{-10,10}]/RandomInteger[{1,10}],b->RandomInteger[{-10,10}]/RandomInteger[{1,10}],c->RandomInteger[{-10,10}]/RandomInteger[{1,10}]},{1000}]//Union

gcd(a,lcm(a,b))==(Abs[a])

FullSimplify[GCD[a,LCM[a,b]],(a|b)∈Integers]

FullSimplify[GCD[a,LCM[a,b]],(a|b)∈Rationals]

Table[GCD[a,LCM[a,b]]-Abs[a]/.{a->RandomInteger[{-10,10}]/RandomInteger[{1,10}],b->RandomInteger[{-10,10}]/RandomInteger[{1,10}]},{100}]//Union

Plots

ListPlot[Union[Flatten[Table[{m/n,LCM[1,m/n]},{m,1000},{n,1000}],1]],PlotRange->{{0,5},{0,20}}]

Show[GraphicsArray[
{
With[{n=64},
ListDensityPlot[Table[LCM[i,j],{i,-n,n},{j,-n,n}],ColorFunction->(Hue[#]&),Mesh->False,FrameLabel->TraditionalForm/@{i,j},
PlotLabel->TraditionalForm[LCM[i,j]],DisplayFunction->Identity]
],
With[{n=512},
ListDensityPlot[Abs[Fourier[Table[LCM[i,j],{i,n},{j,n}]]],ColorFunction->Hue,Mesh->False,FrameLabel->TraditionalForm/@{i,j},
PlotLabel->TraditionalForm[ℱ[LCM[i,j]]],DisplayFunction->Identity]
],
With[{n=512},
ListDensityPlot[Abs[Fourier[Table[1/LCM[i,j],{i,n},{j,n}]]],ColorFunction->Hue,Mesh->False,FrameLabel->TraditionalForm/@{i,j},
PlotLabel->TraditionalForm[ℱ[Superscript[LCM[i,j],-1]]],DisplayFunction->Identity]
]
}]]

Rational

Table[Numerator[m/n]-LCM[1,m/n],{m,10},{n,10}]

Table[Numerator[m/n],{m,10},{n,10}]

Tables

Table[LCM@@Range[n],{n,10}]

MakeBoxes[ylabel,TraditionalForm]:=RowBox[{RowBox[{"ln","(",RowBox[{"LCM","(",RowBox[{"1",",","2",",","…",",","n"}],")"}],")"}],"/","n"}]

With[{max=1000},
ListPlot[Log[Table[LCM@@Range[k],{k,max}]]/Range[max],PlotJoined->True,PlotStyle->Red,AxesLabel->TraditionalForm/@{n,ylabel}]
]

Inequalities

l=Table[LCM@@Range[n],{n,(10^4)}];//Timing

l=Table[LCM@@Range[n],{n,(10^5)}];//Timing

Position[MapIndexed[#1>(2^(#2[[1]]-2))&,l],False]//Flatten

Position[MapIndexed[#1>(2^(#2[[1]]))&,l],False]//Flatten

Position[MapIndexed[#1==(2^(#2[[1]]))&,l],True]//Flatten