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)
Numerical Manipulation (7)
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)
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 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)
The arguments must be explicit integers:
GCD sorts its arguments:
Wolfram Research (1988), GCD, Wolfram Language function, https://reference.wolfram.com/language/ref/GCD.html (updated 1999).
Wolfram Language. 1988. "GCD." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 1999. https://reference.wolfram.com/language/ref/GCD.html.
Wolfram Language. (1988). GCD. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GCD.html