---
tag: 02WF878BH1
kind: definition
name: Greatest common divisor
aliases: [gcd, greatest-common-factor, highest-common-factor]
msc: [11A05]
defines: 0C8WYW4KYQ
uses: [096PW7Q014]
sources:
  - url: https://en.wikipedia.org/wiki/Greatest_common_divisor
    locator: Definition
---

## Definition

Let $a$ and $b$ be integers that are not both $0$.
A common divisor of $a$ and $b$ is an integer $d$ such that $d \mid a$ and $d \mid b$.
The greatest common divisor $\gcd(a, b)$ is the largest common divisor of $a$ and $b$.
By convention, $\gcd(0, 0) = 0$.

## Remarks

The number $\gcd(a, b)$ is positive when $a$ and $b$ are not both $0$, because $1$ is a common divisor.
An equivalent definition: $\gcd(a, b)$ is the unique nonnegative common divisor of $a$ and $b$ that each common divisor [[divides|096PW7Q014]]. This form also gives $\gcd(0, 0) = 0$.
For all integers $a$, $\gcd(a, 0) = |a|$.
The [[Euclidean algorithm|0TRNT4X7J0]] computes $\gcd(a, b)$.

## Explanations

### L1 human

List the positive divisors of each number, and take the largest number that is in both lists.
The divisors of $12$ are $1, 2, 3, 4, 6, 12$, and the divisors of $18$ are $1, 2, 3, 6, 9, 18$.
Thus $\gcd(12, 18) = 6$.