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

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)

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: