GCD
GCD[n1,n2,…]
gives the greatest common divisor of the ni.
Details
- GCD is also known as the greatest common factor or highest common factor.
- Integer mathematical function, suitable for both symbolic and numerical manipulation.
- GCD[n1,n2,…] is the largest positive integer that divides each of the integers n1,n2,….
- For rational numbers ri, GCD[r1,r2,…] gives the greatest rational number r for which all the ri/r are integers.
- GCD works over Gaussian integers.
Examples
open all close allBasic Examples (2)
Scope (11)
Numerical Evaluation (7)
GCD works over integers:
GCD[-12, 9, 57]GCD[-3 + 2I, 10 + 15I]GCD[1 / 3, 2 / 5, 3 / 7]GCD[5 + 10 / 3I, 3 / 2 + I]The one-argument form is identity for positive integers:
GCD[4]The zero-argument form is zero:
GCD[]GCD[20!, 10 ^ 100 + 3]GCD threads elementwise over lists:
GCD[12, {3, 7, 40}]Symbolic Manipulation (4)
TraditionalForm formatting:
TraditionalForm[GCD[n, m]]Reduce[GCD[a, 12] > GCD[a ^ 2 - 1, 12] && -10 < a < 10, a, Integers]Solve[GCD[m, n] == n ^ 2 - n && 1 < n < 10 && 1 < m < 10, {m, n}, Integers]FullSimplify[GCD[p, q], {p, q}∈Primes && p ≠ q]FullSimplify[LCM[m, n]GCD[m, n], {m, n}∈Integers]Applications (11)
Basic Applications (3)
Table of the GCDs of the first 100 pairs of integers:
Grid[Table[If[i * j == 0 , If[i + j == 0, "", Style[i + j, Red, Italic, Bold]], GCD[i, j]], {i, 0, 10}, {j, 0, 10}], ...]Visualize the GCDs of two integers:
ArrayPlot[Table[GCD[m, n], {m, 50}, {n, 50}]]ArrayPlot[Mod[Table[GCD[Fibonacci[j], Fibonacci[k]], {j, 100}, {k, 100}], Fibonacci[11]]]Compute GCD for positive integers:
gcd[a0_, b0_] := Module[{a = a0, b = b0}, While[b ≠ 0, {a, b} = {b, Mod[a, b]};];a];gcd[14, 105]GCD[14, 105]Number Theory (8)
Total@Table[EulerPhi[k], {k, Intersection[Divisors[24], Divisors[12]]}]GCD[24, 12]With[{m = 6, n = 21}, 2Sum[Floor[k n / m], {k, 1, m - 1}] + m + n - m n]GCD[6, 21]Plot the means of the GCDs for successive "balls" of numbers:
ListLinePlot[Table[Mean[Flatten[Table[GCD[i, j], {i, n}, {j, i - 1}]]], {n, 2, 100}]]Conditions for solvability of a linear congruence equation:
Reduce[6 x == 11, x, Modulus -> 3]Mod[GCD[6, 3], 3] == 0Find the fraction of pairs of the first 100 numbers that are relatively prime:
Total[Boole[Table[GCD[m, n] == 1, {m, 100}, {n, 100}]], 2] / 10 ^ 4//N
N[1 / Zeta[2]]The determinant of the matrix of pairwise GCDs is related to Euler's totient function:
Table[Det[Outer[GCD, Range[n], Range[n]]], {n, 1, 12}]Table[Product[EulerPhi[m], {m, 1, n}], {n, 1, 12}]The probability that k random integers have greatest common divisor d is 
:
k = 2;
d = 5;data = Table[GCD@@RandomInteger[1000, k], 10 ^ 6];𝒟 = HistogramDistribution[data];DiscretePlot[#[𝒟, x], {x, 0, 6, .01}, PlotLabel -> #, PlotRange -> All]& /@ {PDF, CDF}PDF[𝒟, 5](d ^ (-k)) / Zeta[k]//NSimplify expressions containing GCD:
FullSimplify[GCD[p, q], {p, q}∈Primes && p ≠ q]FullSimplify[GCD[GCD[m, n], p] - GCD[m, GCD[n, p]], {m, n, p}∈Integers]FullSimplify[LCM[m, n]GCD[m, n], {m, n}∈Integers]FullSimplify[GCD[GCD[l, m], n], {l, m, n}∈Integers]Properties & Relations (8)
Every common divisor of a and b is a divisor of 
:
Divisible[GCD[18, 30], Intersection[Divisors[18], Divisors[30]]]GCD for prime numbers is 
:
GCD[7, 11, 29]GCD for prime power representation 
.
nvec = {1, 2, 3, 4, 5};
mvec = {5, 4, 3, 2, 1};GCD[Subsuperscript[∏, i = 1, 5]Prime[i]^nvec[[i]], Subsuperscript[∏, i = 1, 5]Prime[i]^mvec[[i]]] == Subsuperscript[∏, i = 1, 5]Prime[i]^Min[nvec[[i]], mvec[[i]]]ExtendedGCD gives integers x and y that satisfy 
for some integers a and b:
{g, {x, y}} = ExtendedGCD[24, 36]24x + 36y == gUse CoprimeQ to check for trivial GCDs:
CoprimeQ[5, 6]GCD[5, 6] == 1TrueA GCD property of Fibonacci numbers:
n = 10;m = 11;GCD[Fibonacci[n], Fibonacci[m]] == Fibonacci[GCD[n, m]]Non-negative integers a, b and n satisfy 
:
a = 15;
b = 21;
n = 3;GCD[n ^ a - 1, n ^ b - 1] == n ^ GCD[a, b] - 1GCD is commutative 
:
FullSimplify[GCD[a, b] == GCD[b, a], {a, b}∈Integers]GCD is associative 
:
FullSimplify[GCD[a, GCD[b, c]] == GCD[GCD[a, b], c], {a, b, c}∈Integers]GCD is distributive 
:
FullSimplify[m GCD[a, b] == GCD[m a, m b], {a, b, m}∈Integers && m > 0]Possible Issues (3)
GCD[-3, 9]The arguments must be explicit integers:
GCD[2.4, 5]
GCD sorts its arguments:
GCD[b, a]Interactive Examples (1)
Neat Examples (4)
Plot the arguments of the Fourier transform of the GCD:
ArrayPlot[Arg[Fourier[Table[GCD[m, n], {m, 100}, {n, 100}]]], ColorFunction -> Hue]Plot the absolute values of the Fourier transform of the GCD:
ArrayPlot[Abs[Fourier[Table[GCD[i, j], {i, 100}, {j, 100}]]], ColorFunction -> Hue]Plot the Ulam spiral of the GCD:
ulam[n_] := Partition[Permute[Range[n ^ 2], Accumulate[Take[Flatten[{{n ^ 2 + 1} / 2, Table
[(-1) ^ j i, {j, n}, {i, {-1, n}}, {j}]}], n ^ 2]]], n]ArrayPlot[GCD[ulam[125], 45], ColorFunction -> "BlueGreenYellow"]Form the GCDs of 
with rational numbers:
ListPlot[{#, GCD[1, #]}& /@ Union[Flatten[Table[i / j, {j, 40}, {i, 2j}]]]]
MathWorld
The Wolfram Functions Site
An Elementary Introduction to the Wolfram Language
NKS|OnlineText
Wolfram Research (1988), GCD, Wolfram Language function, https://reference.wolfram.com/language/ref/GCD.html (updated 1999).
CMS
Wolfram Language. 1988. "GCD." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 1999. https://reference.wolfram.com/language/ref/GCD.html.
APA
Wolfram Language. (1988). GCD. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GCD.html