Coprime Integers

Definition

Two integers $a$ and $b$, not both zero, are called coprime if their greatest common divisor is $1$:

They are also called relatively prime.

Coprimality means that $a$ and $b$ have no common positive divisor except $1$. For example,

so $8$ and $15$ are coprime.

The integers themselves need not be prime. Both $8$ and $15$ are composite, but they share no prime factor.

Examples

The integers $14$ and $25$ are coprime because

and the two factorizations have no prime factor in common.

The integers $18$ and $30$ are not coprime because

Indeed,

They share the prime factors $2$ and $3$.

Bezout Criterion

Bezout’s identity gives a fundamental test for coprimality.

Integers $a$ and $b$ are coprime if and only if there exist integers $x$ and $y$ such that

If

then Bezout’s identity gives the equation above.

Conversely, suppose

Any common divisor of $a$ and $b$ must divide every linear combination of $a$ and $b$. Hence it divides $1$. Therefore the greatest common divisor of $a$ and $b$ is $1$.

This criterion is often more useful than the definition because it gives explicit coefficients.

Euclid’s Lemma

A central consequence of coprimality is Euclid’s lemma.

If

and

then

To prove this, use Bezout’s identity. Since $\gcd(a,b)=1$, there exist integers $x$ and $y$ such that

Multiplying by $c$, we get

Now $a\mid acx$ clearly. Also, $a\mid bc$ by assumption, so

Therefore $a$ divides the sum

Hence

Euclid’s lemma is one of the key ingredients in the proof of unique prime factorization.

Pairwise Coprime Integers

A collection of integers

is called pairwise coprime if

whenever

For example,

are pairwise coprime because

Pairwise coprimality is stronger than saying that all numbers have no common divisor greater than $1$.

For example,

have no common divisor greater than $1$, since

But they are not pairwise coprime because

Coprimality and Products

Coprimality behaves well with products.

If

and

then

This follows from Bezout’s identity. Choose integers $x,y,u,v$ such that

and

Multiplying the two equations gives

Expanding,

Thus $1$ is an integer linear combination of $a$ and $bc$, so

This property is frequently used in factorization and congruence arguments.

Coprimality and Modular Inverses

Coprimality exactly characterizes when modular inverses exist.

An integer $a$ has a multiplicative inverse modulo $n$ if and only if

Indeed, $a$ has an inverse modulo $n$ if there exists an integer $x$ such that

This congruence means that

for some integer $y$. Equivalently,

Thus $1$ is a linear combination of $a$ and $n$, which is equivalent to

For example,

so $7$ has an inverse modulo $26$. One such inverse is $15$, since

Reduced Fractions

Coprimality also describes fractions in lowest terms.

A rational number

with $b\ne0$ is in reduced form if

For example,

is not reduced because

Dividing numerator and denominator by $7$, we get

Since

the fraction is now reduced.

Role in Number Theory

Coprimality expresses arithmetic independence. Two integers may both be large and composite, yet from the viewpoint of divisibility they behave independently when their gcd is $1$.

This idea appears throughout number theory. It governs modular inverses, the Chinese remainder theorem, reduced fractions, multiplicative arithmetic functions, primitive solutions of Diophantine equations, and factorization arguments.

The condition

is therefore one of the most important hypotheses in elementary and modern arithmetic.