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 allclose all

Basic Examples  (2)

Find the greatest common divisor of a set of numbers:

Plot the greatest common divisor for a number with :

Scope  (11)

Numerical Evaluation  (7)

GCD works over integers:

Gaussian 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)

TraditionalForm formatting:

Reduce inequalities:

Solve equations:

Simplify expressions:

Applications  (11)

Basic Applications  (3)

Table of the GCDs of the first 100 pairs of integers:

Visualize the GCDs of two integers:

Fibonacci numbers:

Compute GCD for positive integers:

Compare with:

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 :

Compare with:

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:

Wolfram Research (1988), GCD, Wolfram Language function, https://reference.wolfram.com/language/ref/GCD.html (updated 1999).

Text

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

BibTeX

@misc{reference.wolfram_2024_gcd, author="Wolfram Research", title="{GCD}", year="1999", howpublished="\url{https://reference.wolfram.com/language/ref/GCD.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_gcd, organization={Wolfram Research}, title={GCD}, year={1999}, url={https://reference.wolfram.com/language/ref/GCD.html}, note=[Accessed: 21-November-2024 ]}