What is GCD?

Also known as: greatest common divisor · coprime

Definition 64.10 Primary & Middle School Mathematics · Chapter 64 — Arithmetic: Divisors and Prime Numbers

The greatest common divisor of two positive integers $a$ and $b$ , written $\gcd(a, b)$ , is the largest integer dividing both. When $\gcd(a, b) = 1$ , the integers are called coprime: they share no divisor except $1$ .

Examples

Example 64.13

$360 = 2^3 \times 3^2 \times 5$ and $84 = 2^2 \times 3 \times 7$ . Common primes: $2$ (exponents $3$ and $2$ : keep $2$ ) and $3$ (exponents $2$ and $1$ : keep $1$ ). So

\gcd(360, 84) = 2^2 \times 3 = 12 .

Example 64.15

Compute $\gcd(1071, 462)$ :

\begin{align*} 1071 &= 462 \times 2 + 147, \\ 462 &= 147 \times 3 + 21, \\ 147 &= 21 \times 7 + 0 . \end{align*}

The last nonzero remainder is $21$ : $\gcd(1071, 462) = 21$ .

Read in context →

Definition 29.7 High School Mathematics · Chapter 29 — Arithmetic

Let $a, b$ be integers, not both zero. The greatest common divisor $\gcd(a, b)$ is the largest integer dividing both $a$ and $b$ . When $\gcd(a,b) = 1$ , $a$ and $b$ are said to be coprime.

Examples

Example 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ . Hence $\gcd(252,198) = 18$ .

Read in context →

Examples

Examples

Related terms