gives the greatest common divisor of the ni.
- 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.
Examplesopen allclose all
Basic Examples (2)
Find the greatest common divisor of a set of numbers:
Plot the greatest common divisor for a number with :
Numerical Manipulation (7)
GCD works over integers:
Real rational numbers:
Complex rational numbers:
The one-argument form is identity for positive integers:
The zero-argument form is zero:
Compute for large integers:
GCD threads elementwise over lists:
Symbolic Manipulation (4)
Basic Applications (3)
Table of the GCDs of the first 100 pairs of integers:
Visualize the GCDs of two integers:
Compute GCD for positive integers:
Number Theory (8)
Use EulerPhi to compute GCD:
Use Floor to compute GCD:
Plot the means of the GCDs for successive "balls" of numbers:
Conditions for solvability of a linear congruence equation:
Find the fraction of pairs of the first 100 numbers that are relatively prime:
The result is close to :
The determinant of the matrix of pairwise GCDs is related to Euler's totient function:
The probability that k random integers have greatest common divisor d is :
Simplify expressions containing GCD:
Properties & Relations (8)
Every common divisor of a and b is a divisor of :
GCD for prime numbers is :
GCD for prime power representation .
ExtendedGCD gives integers x and y that satisfy for some integers a and b:
Use CoprimeQ to check for trivial GCDs:
A GCD property of Fibonacci numbers:
Non-negative integers a, b and n satisfy :
GCD is commutative :
GCD is associative :
GCD is distributive :
Possible Issues (3)
Signs are discarded:
The arguments must be explicit integers:
GCD sorts its arguments:
Interactive Examples (1)
Visualize the GCDs of three numbers:
Neat Examples (4)
Plot the arguments of the Fourier transform of the GCD:
Plot the absolute values of the Fourier transform of the GCD:
Plot the Ulam spiral of the GCD:
Form the GCDs of with rational numbers:
Introduced in 1988
Updated in 1999