# Greatest Common Divisors

## Common Divisors

Let $a$ and $b$ be integers, not both zero. An integer $d$ is called a common divisor of $a$ and $b$ if

$$
d\mid a
$$

and

$$
d\mid b.
$$

For example, the positive divisors of $18$ are

$$
1,2,3,6,9,18,
$$

and the positive divisors of $30$ are

$$
1,2,3,5,6,10,15,30.
$$

Their common positive divisors are

$$
1,2,3,6.
$$

The largest of these is $6$. Hence

$$
\gcd(18,30)=6.
$$

## Definition

The greatest common divisor of two integers $a$ and $b$, not both zero, is the largest positive integer $d$ such that

$$
d\mid a
$$

and

$$
d\mid b.
$$

It is denoted by

$$
\gcd(a,b).
$$

The condition that $d$ be positive removes the ambiguity caused by signs. If $d$ divides both $a$ and $b$, then $-d$ also divides both. The greatest common divisor is chosen to be positive.

For example,

$$
\gcd(12,18)=6,
\qquad
\gcd(-12,18)=6.
$$

## Basic Examples

If one integer divides the other, the greatest common divisor is the smaller integer in absolute value. For example,

$$
\gcd(8,24)=8.
$$

If two integers share no positive divisor greater than $1$, their greatest common divisor is $1$. For example,

$$
\gcd(14,25)=1.
$$

If $a\ne0$, then

$$
\gcd(a,0)=|a|.
$$

This follows because every integer divides $0$, and the positive divisors of $a$ are exactly the possible common positive divisors of $a$ and $0$.

## Existence

The greatest common divisor always exists for two integers not both zero.

Indeed, the set of positive common divisors of $a$ and $b$ is nonempty because $1$ divides every integer. It is also finite, since any positive divisor of a nonzero integer $a$ is at most $|a|$. If $a=0$, then $b\ne0$, and any common divisor is at most $|b|$.

Therefore the positive common divisors form a finite nonempty set, so they have a largest element.

## Symmetry and Sign

The greatest common divisor is symmetric:

$$
\gcd(a,b)=\gcd(b,a).
$$

It is also insensitive to signs:

$$
\gcd(a,b)=\gcd(|a|,|b|).
$$

For example,

$$
\gcd(-21,35)=\gcd(21,35)=7.
$$

Thus one may usually reduce questions about greatest common divisors to positive integers.

## Coprime Integers

Two integers $a$ and $b$ are called coprime, or relatively prime, if

$$
\gcd(a,b)=1.
$$

For example,

$$
\gcd(8,15)=1,
$$

so $8$ and $15$ are coprime.

Coprime integers need not be prime individually. The integers $8$ and $15$ are both composite, yet they share no common positive divisor greater than $1$.

Coprimality measures shared factor structure, not primality of the individual numbers.

## Prime Factorization View

If the prime factorizations of $a$ and $b$ are known, their greatest common divisor can be read off directly.

For example,

$$
72=2^3\cdot3^2
$$

and

$$
120=2^3\cdot3\cdot5.
$$

The common prime powers are

$$
2^3
\quad\text{and}\quad
3.
$$

Therefore

$$
\gcd(72,120)=2^3\cdot3=24.
$$

In general, the greatest common divisor contains exactly the prime powers that occur in both integers, with the smaller exponent chosen.

## Divisibility Characterization

If

$$
d=\gcd(a,b),
$$

then every common divisor of $a$ and $b$ divides $d$.

This property is deeper than the definition as the largest common divisor. It will follow naturally from Bézout identities after the Euclidean algorithm is developed.

For example, since

$$
\gcd(18,30)=6,
$$

every common divisor of $18$ and $30$ divides $6$.

The common divisors are therefore precisely the divisors of the greatest common divisor.

## Greatest Common Divisors and Linear Combinations

A central theorem states that $\gcd(a,b)$ can be written as an integer linear combination of $a$ and $b$:

$$
\gcd(a,b)=ax+by
$$

for some integers $x$ and $y$.

For example,

$$
\gcd(18,30)=6
$$

and

$$
6=30-18.
$$

Thus

$$
6=(-1)18+1\cdot30.
$$

This representation is known as Bézout's identity. It gives the greatest common divisor a constructive form and is one of the most useful facts in elementary number theory.

## Role in Number Theory

Greatest common divisors measure the shared arithmetic content of integers. They occur in divisibility problems, reduction of fractions, modular inverses, Diophantine equations, and the Chinese remainder theorem.

For example, the fraction

$$
\frac{a}{b}
$$

is in lowest terms precisely when

$$
\gcd(a,b)=1.
$$

A linear congruence

$$
ax\equiv c\pmod n
$$

is solvable exactly when

$$
\gcd(a,n)\mid c.
$$

Thus the greatest common divisor is one of the main organizing invariants of elementary number theory.