# Coprime Integers

## Definition

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

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

They are also called relatively prime.

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

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

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

$$
14=2\cdot7,
\qquad
25=5^2,
$$

and the two factorizations have no prime factor in common.

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

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

Indeed,

$$
18=2\cdot3^2,
\qquad
30=2\cdot3\cdot5.
$$

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

$$
ax+by=1.
$$

If

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

then Bezout's identity gives the equation above.

Conversely, suppose

$$
ax+by=1.
$$

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

$$
a\mid bc
$$

and

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

then

$$
a\mid c.
$$

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

$$
ax+by=1.
$$

Multiplying by $c$, we get

$$
acx+bcy=c.
$$

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

$$
a\mid bcy.
$$

Therefore $a$ divides the sum

$$
acx+bcy.
$$

Hence

$$
a\mid c.
$$

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

## Pairwise Coprime Integers

A collection of integers

$$
a_1,a_2,\ldots,a_n
$$

is called pairwise coprime if

$$
\gcd(a_i,a_j)=1
$$

whenever

$$
i\ne j.
$$

For example,

$$
5,8,9
$$

are pairwise coprime because

$$
\gcd(5,8)=1,
\qquad
\gcd(5,9)=1,
\qquad
\gcd(8,9)=1.
$$

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

For example,

$$
6,10,15
$$

have no common divisor greater than $1$, since

$$
\gcd(6,10,15)=1.
$$

But they are not pairwise coprime because

$$
\gcd(6,10)=2,
\quad
\gcd(6,15)=3,
\quad
\gcd(10,15)=5.
$$

## Coprimality and Products

Coprimality behaves well with products.

If

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

and

$$
\gcd(a,c)=1,
$$

then

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

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

$$
ax+by=1
$$

and

$$
au+cv=1.
$$

Multiplying the two equations gives

$$
(ax+by)(au+cv)=1.
$$

Expanding,

$$
a(axu+xcv+buy)+bc(yv)=1.
$$

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

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

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

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

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

$$
ax\equiv1\pmod n.
$$

This congruence means that

$$
ax-1=ny
$$

for some integer $y$. Equivalently,

$$
ax-ny=1.
$$

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

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

For example,

$$
\gcd(7,26)=1,
$$

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

$$
7\cdot15=105\equiv1\pmod{26}.
$$

## Reduced Fractions

Coprimality also describes fractions in lowest terms.

A rational number

$$
\frac ab
$$

with $b\ne0$ is in reduced form if

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

For example,

$$
\frac{14}{21}
$$

is not reduced because

$$
\gcd(14,21)=7.
$$

Dividing numerator and denominator by $7$, we get

$$
\frac{14}{21}=\frac{2}{3}.
$$

Since

$$
\gcd(2,3)=1,
$$

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

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

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