Coprime Integers
Two integers $a$ and $b$, not both zero, are called coprime if their greatest common divisor is $1$:
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.