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 Manipulation  (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:

Introduced in 1988
 (1.0)
 |
Updated in 1999
 (4.0)
2020
 (12.1)