Greatest common divisor

From AoPSWiki

(Redirected from GCD)

The greatest common divisor (GCD, or GCF (greatest common factor)) of two or more integers is the largest integer that is a divisor of all the given numbers.

The GCD is sometimes called the greatest common factor (GCF).

A very useful property of the GCD is that it can be represented as a sum of the given numbers with integer coefficients. From here it immediately follows that the greatest common divisor of several numbers is divisible by any other common divisor of these numbers.

Finding the GCD

Using prime factorization

Once the prime factorizations of the given numbers have been found, the greatest common divisor is the product of all common factors of the numbers.

Example:

$270=2\cdot3^3\cdot5$ and $144=2^4\cdot3^2$ . The common factors are 2 and $3^2$ , so $GCD(720,144)=2\cdot3^2=18$ .

Euclidean algorithm

The Euclidean algorithm is much faster and can be used to give the GCD of any two numbers without knowing their prime factorizations. To find the greatest common divisor of more than two numbers, one can use the recursive formula $GCD(a_1,\dots,a_n)=GCD(GCD(a_1,\dots,a_{n-1}),a_n)$ .

Using least common multiple

The GCD of two numbers can also be found using the equation $GCD(x, y) \cdot LCM(x, y) = x \cdot y$ , where $LCM(x,y)$ is the least common multiple of $x$ and $y$ .

Personal tools

Navigation

Search

Toolbox