Greatest common divisor ($\gcd$)

For integers $a,b$ not both zero, their greatest common divisor is the largest positive integer dividing both. It is unchanged by replacing either input by its negative. The convention $\gcd (0,0)=0$ is useful, but this exceptional value is not a largest positive common divisor. For positive inputs, the Euclidean algorithm computes the answer, and Bézout's identity expresses it as an integer linear combination of the inputs.

For $12=2^2\cdot 3$ and $18=2\cdot 3^2$, a common divisor can contain at most one copy of the prime number two and one of the prime number three. Taking the smaller prime valuation at each prime number therefore givesThe check $6=18-12$ is also a Bézout's identity: every common divisor divides this difference, and six itself divides both inputs. More generally, every common divisor divides the greatest common divisor, a stronger statement than merely being no larger than it. The companion least common multiple takes the larger prime valuations, as the diagram there illustrates. For an application, divide the numerator and denominator of the fraction $12/18$ by six to obtain $2/3$; these remaining integers are coprime.

For positive integers $m,n,k$, the greatest common divisor scales by the common multiplier $k$. If $d=\gcd (m,n)$, then $kd$ is a common divisor of $km,kn$. Meanwhile Bézout's identity expresses $kd$ as an integer linear combination of $km,kn$, so their greatest common divisor divides $kd$. These two comparisons prove the identity without prime factorization.

Two integers $a,b$ are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use $\gcd (a,b)=\gcd (|a|,|b|)$, with absolute values; changing either sign leaves coprimality unchanged. With the convention $\gcd (0,0)=0$, zero is coprime precisely to $1,-1$, because $\gcd (a,0)=|a|$. Both $1,-1$ are coprime to every integer. ^[ref]

The word concerns shared prime factors, not whether either input is a prime number. For instance $8=2^3$ and $9=3^2$ are coprime composite numbers, even though neither is a square-free integer. Conversely, $6=2\cdot 3$ and $10=2\cdot 5$ are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of $n,n+1$ divides their difference one. Thus $14,15$ provide another pair of coprime composite numbers.

For positive integers, let $P(n)$ be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.

For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, $4,9,25$ have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. ^[ref]

One use is simplifying fractions. For a fraction $a/b$ with integer entries and $b>0$, divide its numerator and denominator by $d=\gcd (a,b)$ to obtain a reduced fraction with coprime entries. For example, $42/30=7/5$ since $d=6$, and $-42/30=-7/5$ uses the same $d$. A further common divisor would make $d$ too small, so the reduction is complete. In particular, the reduced fraction for zero is $0/1$.

Another use is reversible modular arithmetic: for an integer modulus $m>1$, an integer $a$ has a modular inverse precisely when $a,m$ are coprime. The proof outline uses Bézout's identity: $ua+vm=1$ makes $u$ a modular inverse, and any inverse relation $ua-km=1$ forces every common divisor to divide one. For example, $3\cdot 5-2\cdot 7=1$ gives $5^{-1}\equiv 3(\mathrm{mod}7)$, whereas $6$ has no modular inverse modulo $10$. Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. ^[ref]

A list of integers $a_1,\dots ,a_r$, with $r\ge 2$, has pairwise coprimality when every two entries in distinct positions are coprime. This implies joint coprimality. For positive integers, it means no prime factor occurs in two different entries. For example, $4,9,25$ satisfy this condition.

A list of integers $a_1,\dots ,a_r$, with $r\ge 2$, has joint coprimality when its greatest common divisor is one; define that greatest common divisor by repeated application of the two-input operation. For positive integers, no prime factor may divide every entry. Thus $6,10,15$ have joint coprimality but fail pairwise coprimality. For two entries, the conditions coincide.