Two integers are coprime, or relatively prime, if their greatest common divisor is 1. Equivalently, no integer greater than 1 divides both of them. Coprimality describes a relationship between numbers, not a property of either number considered alone: for example, 8 and 15 are coprime even though neither is prime. The concept is fundamental in number theory, particularly in the study of divisibility, fractions, and congruences.
Definition and elementary examples
Integers and are coprime precisely when
The notation is sometimes used, although writing the greatest-common-divisor condition avoids ambiguity.
Examples include:
- and , whose positive divisors have only 1 in common.
- and , despite both numbers being composite.
- Any two distinct prime numbers.
- Any two consecutive integers, since a common divisor of and must divide their difference, 1.
By contrast, 14 and 21 are not coprime because their greatest common divisor is 7.
Signs do not affect coprimality:
Thus and 15 are coprime. The integers 1 and are each coprime to every integer. Since , zero is coprime only to 1 and . Under the usual convention , zero is not coprime to itself.
The fundamental theorem of arithmetic gives another characterization: two nonzero integers are coprime exactly when their absolute values have no prime factor in common.
Bézout’s identity
A central characterization of coprimality is Bézout’s identity:
Thus two integers are coprime precisely when 1 can be expressed as an integer linear combination of them.
For example,
which proves that 8 and 15 are coprime.
One direction follows immediately: if , every common divisor of and divides the left-hand side and therefore divides 1. The reverse direction follows from the extended Euclidean algorithm, which constructs suitable coefficients and .
More generally, if , then there are integers such that
Consequently, a linear Diophantine equation
with not both zero, has an integer solution exactly when divides . When and are coprime, every integer can occur on the right-hand side.
Testing coprimality
The Euclidean algorithm tests coprimality without requiring prime factorization. It repeatedly applies
until the remainder is zero. The last nonzero remainder is the greatest common divisor.
For example,
Hence . Substituting backward gives
The number of Euclidean division steps grows at most logarithmically with the smaller positive input. This makes greatest-common-divisor computation practical even for large integers.
A basic invariance property is
for every integer . Adding a multiple of one number to the other does not change their common divisors.
Several integers: collective and pairwise coprimality
For a finite collection , two distinct conditions must be distinguished.
Collective coprimality means
No integer greater than 1 divides every member of the collection.
Pairwise coprimality means
Every pair must be coprime.
Pairwise coprimality implies collective coprimality, but the converse fails for collections of three or more integers. For example,
yet the pairwise greatest common divisors are 2, 3, and 5. By contrast, 8, 9, and 25 are pairwise coprime.
The terms “mutually coprime” and “relatively prime” are not always used consistently for larger collections. An explicit greatest-common-divisor condition or the word “pairwise” removes ambiguity.
Divisibility consequences
Coprimality allows factors to be separated in divisibility arguments. An important result is Euclid’s lemma in its coprime form:
To see this, multiply a Bézout identity by :
Both terms on the left are divisible by , so is also divisible by .
Other useful consequences include:
If , , and are coprime, then .
If is coprime to both and , then it is coprime to .
For positive integers ,
For positive integers ,
Thus coprimality is equivalent to their least common multiple being .
Fractions and modular arithmetic
Reduced fractions
A fraction , with , is in lowest terms when
Dividing numerator and denominator by their greatest common divisor produces such a representation.
Every rational number has a unique expression with and coprime. The sign convention on the denominator is necessary for uniqueness.
Modular inverses
In modular arithmetic, an integer has a multiplicative inverse modulo , where , exactly when
Indeed, an inverse is an integer satisfying
which is equivalent to an equation for some integer .
For example,
shows that 3 is the inverse of 12 modulo 35.
The invertible residue classes modulo form a group under multiplication. Their number is Euler’s totient function . Euler’s theorem states that
whenever .
Simultaneous congruences
The Chinese remainder theorem states that congruences with pairwise coprime positive moduli have a simultaneous solution, unique modulo the product of those moduli.
For two moduli, if , then
has exactly one solution class modulo , regardless of the residues . Without coprimality, compatibility conditions are needed.
Frequency among positive integers
The proportion of ordered pairs of positive integers at most that are coprime approaches
This limiting density is often described as the probability that two randomly chosen positive integers are coprime. Strictly speaking, there is no uniform probability distribution on all positive integers; the statement refers to independent uniform choices from , followed by the limit as increases.
The result can be expressed using the Riemann zeta function:
For each prime , the factor excludes pairs whose two entries are both divisible by . A rigorous argument justifies passing from finitely many primes to the infinite product.
More generally, for , the limiting proportion of ordered -tuples with collective greatest common divisor 1 is . This is not the density of pairwise coprime -tuples when .
Historical and algebraic context
Relatively prime numbers appear in Euclid’s *Elements*, where they are characterized as numbers measured by the unit alone as a common measure. The Euclidean algorithm provides the classical computational basis for determining this relationship.
In abstract algebra, Bézout’s characterization connects integer coprimality with ideals. In the ring of integers,
The ideal generated by and is therefore the whole ring.
This formulation extends to the notion of comaximal ideals in other rings. However, the integer equivalence between having no common nonunit divisor and generating the whole ring does not hold in every ring, so generalizations of coprimality require care.