Greatest Common Divisor

Author

Eric W. Weisstein
September 10, 2008

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

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

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

Plot

<<Utilities`Typesetting`

ListPlot[Union[Flatten[Table[{m/n,GCD[1,m/n]},{m,200},{n,200}],1]],PlotRange->{{0,3},{0,1.05}},AspectRatio->Automatic,AxesLabel->TraditionalForm/@{m/n,GCD[1,m/n]},PlotRange->All,ImageSize->500]

Array

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

GCD Array

Table[GCD[1,m/n],{m,10},{n,10}]//TraditionalForm

Recurrence

GCDRecurrenceList[a_Integer?OddQ,b_Integer?OddQ]:=NestWhileList[{#[[2]],Total[##]/(2^IntegerExponent[Total[##],2])}&,{a,b},UnsameQ,2]
GCDRecurrence[a_Integer?OddQ,b_Integer?OddQ]:=NestWhile[{#[[2]],Total[##]/(2^IntegerExponent[Total[##],2])}&,{a,b},UnsameQ,2][[1]]

GCDRecurrence[35,15]

GCDRecurrenceList[35,15]

Subtract@@@Flatten[Table[{GCDRecurrence[a,b],GCD[a,b]},{a,1,200,2},{b,1,200,2}],1]//Union

ArrayPlot[Table[Length[GCDList[a,b]-2],{a,1,200,2},{b,1,200,2}],ColorFunction->Hue,DataRange->{{1,199},{1,199}},ColorFunctionScaling->True,FrameLabel->TraditionalForm/@{a,b},FrameTicks->True]

Identities

gcd(a m,b m)==|m| gcd(a,b)

FunctionExpand[GCD[m a,m b],(m|a|b)∈Integers]

gcd(a m,b m,c m)==m gcd(a,b,c)

FunctionExpand[GCD[m a,m b,m c],(m|a|b|c)∈Integers]

FunctionExpand[GCD[m a,m b,m c],(m|a|b|c)∈Integers&&a>0&&b>0&&c>0]

FunctionExpand[GCD[m a,m b,m c],(m|a|b|c)∈Integers&&0<a<b<c]

gcd(gcd(a,b),c)==gcd(a,b,c)

GCD[GCD[a,b],c]

GCD[a,GCD[b,c]]

gcd(a b,c d)==gcd(a,c) gcd(b,d) gcd((a/(gcd(a,c))),(d/(gcd(b,d)))) gcd((c/(gcd(a,c))),(b/(gcd(b,d))))

GCD[a b,c d]

FunctionExpand[GCD[a b,c d],(a|b|c|d)∈Integers&&a>0&&b>0&&c>0&&d>0]

FullSimplify[GCD[a,c]GCD[b,d]GCD[(a/(GCD[a,c])),(d/(GCD[b,d]))]GCD[(c/(GCD[a,c])),(b/(GCD[b,d]))],(a|b|c|d)∈Integers&&a>0&&b>0&&c>0&&d>0]

FullSimplify[GCD[a b,c d]-GCD[a,c]GCD[b,d]GCD[(a/(GCD[a,c])),(d/(GCD[b,d]))]GCD[(c/(GCD[a,c])),(b/(GCD[b,d]))],(a|b|c|d)∈Integers&&a>0&&b>0&&c>0&&d>0]

Subtract@@@Flatten[Table[{GCD[a b,c d],GCD[a,c]GCD[b,d]GCD[(a/(GCD[a,c])),(d/(GCD[b,d]))]GCD[(c/(GCD[a,c])),(b/(GCD[b,d]))]},{a,10},{b,10},{c,10},{d,10}],3]//Union

gcd(a,a)==|a|

GCD[a,a]

FunctionExpand[GCD[a,a],a∈Integers]

FullSimplify[GCD[a,a],a∈Integers]

gcd(b,a)==gcd(a,b)

GCD[b,a]

GCD[b,a]-GCD[a,b]

gcd((2^p)-1,(2^q)-1)==(2^(gcd(p,q)))-1

FunctionExpand[GCD[(2^p)-1,(2^q)-1],(p|q)∈Integers&&p>0&&q>0]

Subtract@@@Flatten[Table[{GCD[(2^p)-1,(2^q)-1],(2^(GCD[p,q]))-1},{p,100},{q,100}],1]//Union

Misc

lcm[a_Integer,b_Integer]:=Module[{pf=FactorInteger/@{a,b}/.{}->{{1,1}},f,i},
f=Union[Flatten[Transpose[#][[1]]&/@pf]];
Times@@(f^Table[Max@@Transpose[Select[Flatten[pf,1],#[[1]]==f[[i]]&]][[2]],{i,Length[f]}])
]

Union[Table[llcm[m,n]-LCM[m,n] /. {m->Random[Integer,{1,100}],n->Random[Integer,{1,100}]},{100}]]

Table[gcd[m,n]-GCD[m,n] /. {m->Random[Integer,{1,100}],n->Random[Integer,{1,100}]},{1}]

gcd[2,3]

GCD[2,3]

FactorInteger[2]