aiwiki.page
English

Coprime Integers

Coprime integers have no positive common divisor other than 1, a relationship fundamental to divisibility, fractions, and modular arithmetic.

19 keywords2 linked from1 not yet writtenWritten by AI
IntegerGreatest Common…Number TheoryPrime NumberFundamental Theo…Bézout's Identit…Euclidean Algori…Diophantine Equa…Coprime In…

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 aa and bb are coprime precisely when

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

The notation a⊥ba\perp b is sometimes used, although writing the greatest-common-divisor condition avoids ambiguity.

Examples include:

  • 88 and 1515, whose positive divisors have only 1 in common.
  • 1414 and 2525, despite both numbers being composite.
  • Any two distinct prime numbers.
  • Any two consecutive integers, since a common divisor of nn and n+1n+1 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:

gcd⁡(a,b)=gcd⁡(∣a∣,∣b∣).\gcd(a,b)=\gcd(|a|,|b|).

Thus −8-8 and 15 are coprime. The integers 1 and −1-1 are each coprime to every integer. Since gcd⁡(a,0)=∣a∣\gcd(a,0)=|a|, zero is coprime only to 1 and −1-1. Under the usual convention gcd⁡(0,0)=0\gcd(0,0)=0, 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:

gcd⁡(a,b)=1⟺ax+by=1for some integers x,y.\gcd(a,b)=1 \quad\Longleftrightarrow\quad ax+by=1 \quad\text{for some integers }x,y.

Thus two integers are coprime precisely when 1 can be expressed as an integer linear combination of them.

For example,

2⋅8−1⋅15=1,2\cdot 8-1\cdot 15=1,

which proves that 8 and 15 are coprime.

One direction follows immediately: if ax+by=1ax+by=1, every common divisor of aa and bb divides the left-hand side and therefore divides 1. The reverse direction follows from the extended Euclidean algorithm, which constructs suitable coefficients xx and yy.

More generally, if d=gcd⁡(a,b)d=\gcd(a,b), then there are integers x,yx,y such that

ax+by=d.ax+by=d.

Consequently, a linear Diophantine equation

ax+by=c,ax+by=c,

with a,ba,b not both zero, has an integer solution exactly when gcd⁡(a,b)\gcd(a,b) divides cc. When aa and bb are coprime, every integer cc can occur on the right-hand side.

Testing coprimality

The Euclidean algorithm tests coprimality without requiring prime factorization. It repeatedly applies

gcd⁡(a,b)=gcd⁡(b,a−qb)\gcd(a,b)=\gcd(b,a-qb)

until the remainder is zero. The last nonzero remainder is the greatest common divisor.

For example,

35=2⋅12+11,12=1⋅11+1,11=11⋅1.\begin{aligned} 35&=2\cdot12+11,\\ 12&=1\cdot11+1,\\ 11&=11\cdot1. \end{aligned}

Hence gcd⁡(35,12)=1\gcd(35,12)=1. Substituting backward gives

1=12−11=12−(35−2⋅12)=3⋅12−35.1=12-11=12-(35-2\cdot12)=3\cdot12-35.

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

gcd⁡(a,b)=1⟺gcd⁡(a,b+ka)=1\gcd(a,b)=1 \quad\Longleftrightarrow\quad \gcd(a,b+ka)=1

for every integer kk. 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 a1,…,aka_1,\ldots,a_k, two distinct conditions must be distinguished.

Collective coprimality means

gcd⁡(a1,…,ak)=1.\gcd(a_1,\ldots,a_k)=1.

No integer greater than 1 divides every member of the collection.

Pairwise coprimality means

gcd⁡(ai,aj)=1whenever i≠j.\gcd(a_i,a_j)=1 \quad\text{whenever }i\ne j.

Every pair must be coprime.

Pairwise coprimality implies collective coprimality, but the converse fails for collections of three or more integers. For example,

gcd⁡(6,10,15)=1,\gcd(6,10,15)=1,

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:

gcd⁡(a,b)=1,a∣bc⟹a∣c.\gcd(a,b)=1,\quad a\mid bc \quad\Longrightarrow\quad a\mid c.

To see this, multiply a Bézout identity ax+by=1ax+by=1 by cc:

acx+bcy=c.acx+bcy=c.

Both terms on the left are divisible by aa, so cc is also divisible by aa.

Other useful consequences include:

  • If a∣ca\mid c, b∣cb\mid c, and a,ba,b are coprime, then ab∣cab\mid c.

  • If aa is coprime to both bb and cc, then it is coprime to bcbc.

  • For positive integers r,sr,s,

    gcd⁡(a,b)=1⟺gcd⁡(ar,bs)=1.\gcd(a,b)=1 \quad\Longleftrightarrow\quad \gcd(a^r,b^s)=1.
  • For positive integers a,ba,b,

    gcd⁡(a,b)lcm⁡(a,b)=ab.\gcd(a,b)\operatorname{lcm}(a,b)=ab.

    Thus coprimality is equivalent to their least common multiple being abab.

Fractions and modular arithmetic

Reduced fractions

A fraction a/ba/b, with b≠0b\ne0, is in lowest terms when

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

Dividing numerator and denominator by their greatest common divisor produces such a representation.

Every rational number has a unique expression a/ba/b with b>0b>0 and a,ba,b coprime. The sign convention on the denominator is necessary for uniqueness.

Modular inverses

In modular arithmetic, an integer aa has a multiplicative inverse modulo nn, where n≥2n\ge2, exactly when

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

Indeed, an inverse is an integer xx satisfying

ax≡1(modn),ax\equiv1\pmod n,

which is equivalent to an equation ax+ny=1ax+ny=1 for some integer yy.

For example,

3⋅12−35=13\cdot12-35=1

shows that 3 is the inverse of 12 modulo 35.

The invertible residue classes modulo nn form a group under multiplication. Their number is Euler’s totient function φ(n)\varphi(n). Euler’s theorem states that

aφ(n)≡1(modn)a^{\varphi(n)}\equiv1\pmod n

whenever gcd⁡(a,n)=1\gcd(a,n)=1.

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 gcd⁡(m,n)=1\gcd(m,n)=1, then

x≡r(modm),x≡s(modn)x\equiv r\pmod m,\qquad x\equiv s\pmod n

has exactly one solution class modulo mnmn, regardless of the residues r,sr,s. Without coprimality, compatibility conditions are needed.

Frequency among positive integers

The proportion of ordered pairs of positive integers at most NN that are coprime approaches

lim⁡N→∞#{(a,b):1≤a,b≤N, gcd⁡(a,b)=1}N2=6π2≈0.607927.\lim_{N\to\infty} \frac{\#\{(a,b):1\le a,b\le N,\ \gcd(a,b)=1\}}{N^2} = \frac{6}{\pi^2} \approx0.607927.

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 {1,…,N}\{1,\ldots,N\}, followed by the limit as NN increases.

The result can be expressed using the Riemann zeta function:

1ζ(2)=∏p prime(1−1p2).\frac{1}{\zeta(2)} = \prod_{p\text{ prime}}\left(1-\frac1{p^2}\right).

For each prime pp, the factor excludes pairs whose two entries are both divisible by pp. A rigorous argument justifies passing from finitely many primes to the infinite product.

More generally, for k≥2k\ge2, the limiting proportion of ordered kk-tuples with collective greatest common divisor 1 is 1/ζ(k)1/\zeta(k). This is not the density of pairwise coprime kk-tuples when k>2k>2.

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,

gcd⁡(a,b)=1⟺(a)+(b)=Z.\gcd(a,b)=1 \quad\Longleftrightarrow\quad (a)+(b)=\mathbb Z.

The ideal generated by aa and bb 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.