In number theory, two integers a and b are defined as coprime, or relatively prime, if their greatest common divisor is 1, meaning they share no common prime factors other than 1.\](https://www.math.cmu.edu/~mradclif/teaching/127S19/Notes/Division.pdf) This property holds if and only if there are no integers greater than 1 that divide both $a$ and $b$, and it applies to any pair of integers, including negatives and zero (with the convention that gcd(0,0) is undefined but gcd(a,0)=|a| for a ≠ 0).\[(http://cse.unl.edu/~cbourke/CSCE235/notes/NumberTheory-HandoutNoNotes.pdf) Examples include 8 and 15 (gcd=1) or 21 and 22 (gcd=1), but not 12 and 18 (gcd=6).$$](https://www.math.uci.edu/~ndonalds/math180a/2unique.pdf)The concept of coprime integers is foundational to many theorems in elementary number theory. Bézout's identity asserts that if a and b are coprime, then there exist integers x and y such that ax + by = 1, providing a linear combination that generates the gcd.[(https://math.gordon.edu/ntic/ntic/section-bezout-id.html) This extends to the more general case where gcd($a,b$)=d, allowing $ax + by = d$.](https://www.cs.dartmouth.edu/~deepc/LecNotes/cs30/lec27.pdf) Euclid's lemma follows as a consequence: if a prime p divides the product ab and p is coprime to a, then p must divide b; this is key to proving the fundamental theorem of arithmetic on unique prime factorization.[$$(https://www.math.uci.edu/~ndonalds/math180a/2unique.pdf)Coprime integers also play a central role in modular arithmetic and cryptographic applications. Euler's theorem states that if a and n are coprime, then a^{\phi(n)} \equiv 1 \pmod{n}, where \phi(n) is Euler's totient function counting the integers from 1 to n-1 that are coprime to n; for primes p, this reduces to Fermat's Little Theorem with \phi(p) = p-1.\](https://mathweb.ucsd.edu/~jmckerna/Teaching/15-16/Spring/103B/l_13.pdf) In the RSA cryptosystem, the public exponent $e$ is selected to be coprime to $\phi(n)$ (where $n = pq$ for distinct primes $p$ and $q$), ensuring $e$ has a modular inverse modulo $\phi(n)$ for decryption.\[(https://www.utdallas.edu/~ivor/dl/rsa.pdf) Additionally, Dirichlet's theorem guarantees infinitely many primes in any arithmetic progression a + kd where a and d > 0 are coprime.$$](https://ocw.mit.edu/courses/18-785-number-theory-i-fall-2021/mit18_785f21_full_lec.pdf)
Definition and Basic Concepts
Definition of Coprimality
Two integers a and b are said to be coprime, or relatively prime, if their greatest common divisor \gcd(a, b) equals 1.[1] The greatest common divisor of a and b is the largest positive integer that divides both without remainder.[2] This condition implies that a and b share no common prime factors other than possibly 1, ensuring they have no nontrivial common divisors.[1]Although the definition applies to all integers, discussions of coprimality often focus on positive integers for simplicity, as the gcd is invariant under signs: \gcd(a, b) = \gcd(|a|, |b|).[3] Special care is needed for zero; \gcd(0, n) = |n| for any integer n \neq 0, so 0 and n are coprime only if |n| = 1.[3] Thus, 0 is coprime with 1 and -1, but not with any other integer.[3]The concept originates in Euclid's Elements (circa 300 BCE), where relatively prime numbers are defined in Book VII, Definition 12 as those "measured by a unit alone as a common measure."[4] This foundational idea underpins the unique factorization of integers into primes, as coprimality guarantees that factorizations do not share common elements beyond unity.[5]For example, 8 and 15 are coprime because \gcd(8, 15) = 1, as 8 factors as $2^3 and 15 as $3 \times 5, with no shared prime factors.[2]
Notation and Testing
Two integers a and b are denoted as coprime if their greatest common divisor satisfies (a, b) = 1, where (a, b) is the standard notation for the gcd.[6] An alternative symbol in some number theory texts is a \perp b, employing the perpendicularity notation to signify that no prime divides both a and b. In computational mathematics and programming libraries, such as those in symbolic algebra systems, a predicate like RelPrime(a, b) may return true if the pair is coprime.[6]The primary method to test coprimality is the Euclidean algorithm, which efficiently computes \gcd(a, b) for integers a > b > 0. The algorithm proceeds recursively: \gcd(a, b) = \gcd(b, a \mod b), continuing until the remainder is zero, at which point the non-zero remainder is the gcd; if this value is 1, then a and b are coprime.[7] This process relies on the property that the gcd remains unchanged under replacement of the larger number by its remainder when divided by the smaller.[8]The Euclidean algorithm has a time complexity of O(\log \min(a, b)), as each step roughly halves the size of the numbers involved, leading to at most a logarithmic number of divisions.[9] For verification purposes, the extended Euclidean algorithm augments the basic version by tracking coefficients to express the gcd as a linear combination: it finds integers s and t such that as + bt = \gcd(a, b); when the gcd is 1, this confirms coprimality via Bézout's identity.[10]Consider the example of testing \gcd(48, 35):[
\begin{align*}
48 &= 1 \cdot 35 + 13, \
35 &= 2 \cdot 13 + 9, \
13 &= 1 \cdot 9 + 4, \
9 &= 2 \cdot 4 + 1, \
4 &= 4 \cdot 1 + 0.
\end{align*}
The last non-zero remainder is 1, so $\gcd(48, 35) = 1$, confirming that 48 and 35 are coprime.[](https://cp-algorithms.com/algebra/euclid-algorithm.html)
## Properties of Coprime Integers
### Arithmetic Properties
A fundamental arithmetic property of coprime integers is their invariance under addition multiples. Specifically, if $\gcd(a, b) = 1$, then $\gcd(a + k b, b) = 1$ for any integer $k$. This follows from the general relation $\gcd(a + k b, b) = \gcd(a, b)$, which holds because any common divisor of $a + k b$ and $b$ also divides $a = (a + k b) - k b$, and conversely, any common divisor of $a$ and $b$ divides $a + k b$.
Bézout's identity provides a characterization of coprimality in terms of linear combinations. It states that two integers $a$ and $b$ are coprime [if and only if](/page/If_and_only_if) there exist integers $x$ and $y$ such that $a x + b y = 1$. More generally, for any integers $a$ and $b$ not both zero, there exist integers $x$ and $y$ such that $a x + b y = \gcd(a, b)$. The proof is constructive and relies on the [extended Euclidean algorithm](/page/Extended_Euclidean_algorithm), which back-substitutes the steps of the [Euclidean algorithm](/page/Euclidean_algorithm) to express the gcd as such a combination, though the explicit steps are omitted here.[](https://mathworld.wolfram.com/BezoutsIdentity.html)
A key consequence is that the set of all [integer](/page/Integer) linear combinations $a x + b y$, where $x$ and $y$ range over the [integers](/page/Integer), consists precisely of the multiples of $\gcd(a, b)$. Thus, when $a$ and $b$ are coprime, these linear combinations generate all [integers](/page/Integer), meaning the [ideal](/page/Ideal) generated by $a$ and $b$ in the [ring of integers](/page/Ring_of_integers) is the entire ring $\mathbb{[Z](/page/Z)}$. For example, the equation $15x + 28y = 1$ has [integer](/page/Integer) solutions, such as $x = -13$ and $y = 7$, since $15(-13) + 28(7) = -195 + 196 = 1$.[](https://mathworld.wolfram.com/BezoutsIdentity.html)
In contrast, if $a$ and $b$ are not coprime, with $\gcd(a, b) = d > 1$, then $d$ divides every [linear combination](/page/Linear_combination) $a x + b y$, including $a + b$. Consequently, $\gcd(a + b, b) = d > 1$, illustrating how non-coprimality propagates under [addition](/page/Addition).
### Multiplicative Properties
One fundamental multiplicative property of coprimality is its preservation under multiplication: if $\gcd(a, b) = 1$ and $\gcd(a, c) = 1$, then $\gcd(a, bc) = 1$.[](https://pennance.us/home/downloads/3325/gcd.pdf) This follows from the fact that any common [divisor](/page/Divisor) of $a$ and $bc$ must divide $b$ and $c$ separately, but since $a$ shares no common factors with either, the gcd remains 1.[](https://webpages.math.luc.edu/~rgoebel1/TeachingArchive/Fall11Math201/pdf/q2sol.pdf)
A more general result is the multiplicative formula for the gcd: if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \cdot \gcd(b, c)$.[](https://www.geeksforgeeks.org/maths/properties-of-gcd/) For example, if $a=2$, $b=3$, and $c=6$, then $\gcd(2,3)=1$ and $\gcd(6,6)=6 = \gcd(2,6) \cdot \gcd(3,6) = 2 \cdot 3$. This property highlights how coprimality allows the gcd to "distribute" over [multiplication](/page/Multiplication) without interference from shared factors.
Coprimality is intimately connected to the unique factorization theorem, which states that every [integer](/page/Integer) greater than 1 has a unique prime [factorization](/page/Factorization) up to ordering. Two [integer](/page/Integer)s are coprime [if and only if](/page/If_and_only_if) they share no common prime factors in their factorizations. For instance, distinct primes $p$ and $q$ are coprime, so $pq$ has the distinct prime factors $p$ and $q$ with multiplicity one each.
This coprimality condition is a prerequisite for [Euler's theorem](/page/Euler's_theorem) in [modular arithmetic](/page/Modular_arithmetic): if $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi$ is [Euler's totient function](/page/Euler's_totient_function).[](https://www.math.uci.edu/~ndonalds/math180a/4euler.pdf)
## Coprimality in Sets
### Pairwise and Mutual Coprimality
In [number theory](/page/Number_theory), a finite set of integers $\{a_1, a_2, \dots, a_k\}$ with $k \geq 2$ is said to be **pairwise coprime** if $\gcd(a_i, a_j) = 1$ for every pair of distinct indices $i \neq j$. This condition ensures that no prime divides more than one element in the set. For example, the set $\{6, 35, 11\}$ is pairwise coprime, as $\gcd(6, 35) = 1$, $\gcd(6, 11) = 1$, and $\gcd(35, 11) = 1$.[](https://t5k.org/glossary/xpage/PairwiseRelativelyPrime.html)[](https://planetcalc.com/9547/)
A set of integers is **mutually coprime** (also called setwise coprime) if the [greatest common divisor](/page/Greatest_common_divisor) of all its elements is 1, that is, $\gcd(a_1, a_2, \dots, a_k) = 1$. This property is weaker than pairwise coprimality, as it only requires that no single prime divides every element in the set, without restricting shared factors between subsets. For instance, the set $\{6, 10, 15\}$ is mutually coprime since $\gcd(6, 10, 15) = 1$, but it is not pairwise coprime because $\gcd(6, 10) = 2 > 1$, $\gcd(6, 15) = 3 > 1$, and $\gcd(10, 15) = 5 > 1$.[](https://oeis.org/wiki/Coprimality)
Pairwise coprimality implies mutual coprimality: if every pair has gcd 1, then no prime can divide all elements, so the overall gcd is 1. The [converse](/page/Converse) does not hold, and the distinction first arises for sets of size 3, as any two integers are either both pairwise and mutually coprime or neither. A key property is that if the elements of a pairwise coprime set are each square-free (divisible by no squared prime greater than 1), then their product is also square-free. This follows from the unique prime factorization theorem, as no prime divides more than one factor, preventing any squared primes in the product.
### Coprime Sets and Sequences
A coprime sequence refers to an infinite sequence of integers where each pair of consecutive terms is coprime, satisfying $\gcd(a_i, a_{i+1}) = 1$ for all $i$. The [Fibonacci sequence](/page/Fibonacci_sequence), defined by $F_1 = 1$, $F_2 = 1$, and $F_k = F_{k-1} + F_{k-2}$ for $k \geq 3$, exemplifies this property, as consecutive terms are always coprime; more generally, $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ for any positive integers $m$ and $n$, ensuring the condition holds since $F_d = 1$ when $d = 1$.[](https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml)
Infinite coprime sets consist of infinitely many integers that are pairwise coprime, meaning $\gcd(a_i, a_j) = 1$ for all distinct $i, j$. The set of all prime numbers serves as a fundamental example, with distinct primes sharing no common prime factors.[](https://t5k.org/glossary/xpage/PairwiseRelativelyPrime.html) Additional constructions include the Fermat numbers $F_n = 2^{2^n} + 1$ for $n \geq 0$, which are pairwise coprime due to the relation $F_m$ dividing $F_n - 2$ for $m < n$, and Sylvester's sequence, defined by $s_0 = 2$ and $s_k = s_{k-1}^2 - s_{k-1} + 1$ for $k \geq 1$, where each term is the product of all previous terms plus one, ensuring pairwise coprimality.[](https://oeis.org/wiki/Coprimality) Such sets highlight the existence of infinite pairwise coprime collections with varying growth rates and densities, from zero asymptotic density in the primes to sparser distributions in sequences like Sylvester's.
A key property connecting coprime integers to sequences is Zsigmondy's theorem, which asserts that if $a$ and $b$ are coprime positive [integers](/page/Integer) with $a > b \geq 1$ and $n > 1$ is an [integer](/page/Integer), then $a^n - b^n$ possesses a primitive prime divisor—a prime $p$ dividing $a^n - b^n$ but no $a^d - b^d$ for $1 \leq d < n$—with exceptions only for $(a, b, n) = (2, 1, 6)$ and cases where $n = 2$ and $a + b$ is a power of 2.[](https://mathworld.wolfram.com/ZsigmondyTheorem.html) This result guarantees new prime factors in sequences like $a^n - b^n$ for coprime bases, aiding analysis of primitivity in cyclotomic polynomials and related constructions.
## Probabilistic Aspects
### Probability of Coprimality
The probability that two randomly selected positive integers $a$ and $b$ are coprime, meaning $\gcd(a, b) = 1$, is a fundamental result in analytic [number theory](/page/Number_Theory). This probability equals $\frac{6}{\pi^2} \approx 0.607927$, indicating that approximately 60.8% of pairs of positive integers share no common prime factors other than 1.[](https://mathworld.wolfram.com/Coprime.html)[](https://projecteuclid.org/journals/statistical-science/volume-35/issue-2/On-the-Probability-That-Two-Random-Integers-Are-Coprime/10.1214/19-STS737.pdf)
The derivation relies on the Euler product formula for the Riemann zeta function $\zeta(s)$. Specifically, the probability $P(\gcd(a, b) = 1)$ is given by the infinite product over all primes $p$:
P(\gcd(a, b) = 1) = \prod_p \left(1 - \frac{1}{p^2}\right),
where the product converges because the sum $\sum_p \frac{1}{p^2}$ is finite. This product equals $\frac{1}{\zeta(2)}$, and since $\zeta(2) = \frac{\pi^2}{6}$, the probability simplifies to $\frac{6}{\pi^2}$. The interpretation arises from the fact that for each prime $p$, the probability that $p$ does not divide both $a$ and $b$ is $1 - \frac{1}{p^2}$, and independence over primes yields the full product.[](https://mathworld.wolfram.com/Coprime.html)[](https://arxiv.org/pdf/1806.00053)
This result traces back to Leonhard Euler's 1737 paper "Variae observationes circa series infinitas," where he established the Euler product for $\zeta(s)$ and evaluated $\zeta(2) = \frac{\pi^2}{6}$ using the infinite product over primes, laying the groundwork for the coprimality probability. The explicit connection to the probability of coprimality follows directly from this product, with convergence ensured by the finiteness of $\zeta(2)$.[](https://scholarlycommons.pacific.edu/euler-works/72/)
In practice, for finite ranges, the proportion of coprime pairs $(a, b)$ with $1 \leq a, b \leq N$ approaches $\frac{6}{\pi^2}$ as $N \to \infty$. The number of such pairs is asymptotically $\frac{6N^2}{\pi^2} + O(N \log N)$, confirming the limiting probability through rigorous error bounds.[](https://arxiv.org/pdf/1806.00053)[](https://projecteuclid.org/journals/statistical-science/volume-35/issue-2/On-the-Probability-That-Two-Random-Integers-Are-Coprime/10.1214/19-STS737.pdf)
### Density and Distribution
The natural density of the set of positive integers coprime to a fixed positive integer $n > 1$ is $\frac{\phi(n)}{n}$, where $\phi$ is [Euler's totient function](/page/Euler's_totient_function). This implies that the number of such integers not exceeding $x$ is asymptotically $\frac{\phi(n)}{n} x$, with an error term bounded by the number of divisors of $n$.[](https://archive.org/details/introductiontoth0000hard_z6j4)
In higher dimensions, the asymptotic density of $k$-[tuples](/page/Tuple) of positive integers $(m_1, \dots, m_k)$ with each $m_i \leq x$ that are pairwise coprime is given by the [infinite product](/page/Infinite_product) over all primes $p$ of the local factor $(1 - 1/p)^{k-1} (1 + (k-1)/p)$, which simplifies for $k=2$ to $6/\pi^2$ and yields smaller values for larger $k$, such as approximately 0.286 for $k=3$. This product arises from the probability that no prime divides more than one member of the tuple at each prime locus, and while it lacks a closed form like the mutual coprimality case, numerical evaluation shows it decreases with $k$. For mutual coprimality (gcd of all $k$ being 1), the density is instead $1/\zeta(k)$, where $\zeta$ is the [Riemann zeta function](/page/Riemann_zeta_function), providing a benchmark for comparison in multidimensional settings.[](https://www.researchgate.net/publication/232252227_The_probability_that_k_positive_integers_are_pairwise_relatively_prime)[](https://archive.org/details/introductiontoth0000hard_z6j4)
The integers coprime to a fixed $n$ exhibit equidistribution properties in arithmetic progressions. Specifically, when $\gcd(m, n) = 1$, these integers are equidistributed [modulo](/page/Modulo) $m$, meaning each residue class $a \pmod{m}$ contains asymptotically the same proportion $\frac{\phi(n)}{n m}$ of them up to $x$. More generally, for progressions $a \pmod{m}$ with $\gcd(a, m) = 1$, the coprime integers align uniformly under compatibility conditions with $n$, reflecting the periodic nature of the set via the [Chinese remainder theorem](/page/Chinese_remainder_theorem).[](https://archive.org/details/introductiontoth0000hard_z6j4)
Despite these average behaviors, the distribution of coprime pairs and tuples displays irregularities and gaps, particularly in short intervals or along specific lines in the [lattice](/page/Lattice). The Hardy-Littlewood conjectures, through the circle method and singular series, predict fine-scale asymptotics for the count of coprime pairs $(m, n)$ with bounded differences or in restricted regions, accounting for local obstructions at primes and suggesting Poisson-like fluctuations around the mean density. These conjectures remain unproved but guide estimates for gaps between consecutive coprime integers or tuples.
## Generating Coprime Pairs
### Algorithms and Methods
One effective method for generating coprime integer pairs involves the use of [Farey sequence](/page/Farey_sequence)s, which systematically enumerate all reduced fractions $ \frac{a}{b} $ where $ 0 \leq a \leq b \leq N $, $ \gcd(a, b) = 1 $, and the fractions are ordered increasingly between 0 and 1. The construction is recursive: begin with the Farey sequence of order 1, $ F_1 = \left( \frac{0}{1}, \frac{1}{1} \right) $. To obtain $ F_n $ from $ F_{n-1} $, insert the [mediant](/page/Mediant) $ \frac{a + c}{b + d} $ between every pair of adjacent fractions $ \frac{a}{b} $ and $ \frac{c}{d} $ in $ F_{n-1} $ whenever $ b + d = n $, ensuring all inserted fractions are in lowest terms. This process generates approximately $ \frac{3N^2}{\pi^2} $ coprime pairs up to denominator $ N $, providing a complete list without duplicates or omissions for the specified range.[](https://cp-algorithms.com/others/stern_brocot_tree_farey_sequences.html)
Sieve-based approaches adapt the [sieve of Eratosthenes](/page/Sieve_of_Eratosthenes) to identify and mark non-coprime pairs within bounds up to $ N $, enabling efficient enumeration of coprime ones. Precompute the smallest prime [factor](/page/Factor) for each [integer](/page/Integer) up to $ N $ using a linear [sieve](/page/Sieve) in $ O(N \log \log N) $ time. Then, for generating pairs $ (a, b) $ with $ 1 \leq a, b \leq N $, iterate over possible values and use the precomputed factors to skip or mark positions sharing common primes, effectively filtering to retain only coprime pairs. This method avoids computing the GCD for every potential pair, reducing redundant operations by leveraging prime multiplicity markings across the range.
For random generation of coprime pairs, rejection sampling offers a straightforward probabilistic [algorithm](/page/Algorithm): select integers $ a $ and $ b $ uniformly at random from $ [1, N] $, compute $ \gcd(a, b) $, and accept the pair if it equals 1; otherwise, reject and resample. The acceptance probability is $ \frac{6}{\pi^2} \approx 0.6079 $, implying an expected $ \frac{\pi^2}{6} \approx 1.64493 $ trials per valid pair, independent of $ N $ for large ranges. This efficiency stems from the asymptotic density of coprime pairs among all integer pairs, derived from the Euler product over primes.[](https://arxiv.org/abs/1806.00053) This efficiency stems from the asymptotic density of coprime pairs among all integer pairs, derived from the Euler product over primes.[](https://projecteuclid.org/journals/statistical-science/volume-35/issue-2/On-the-Probability-That-Two-Random-Integers-Are-Coprime/10.1214/19-STS737.pdf)
The overall [time complexity](/page/Time_complexity) for generating all coprime pairs up to $ N $ using sieve-based methods is $ O(N^2) $, accounting for the [harmonic](/page/Harmonic) summation over primes in the marking process and the output size of approximately $ \frac{6N^2}{\pi^2} $ pairs.
### Constructions and Examples
One of the simplest constructions of coprime [integer](/page/Integer) pairs is the set of consecutive integers $(n, n+1)$ for any [integer](/page/Integer) $n \geq 1$. These pairs are always coprime, as any common [divisor](/page/Divisor) $d > 1$ of $n$ and $n+1$ would also divide their difference $(n+1) - n = 1$, which is impossible.[](https://mathworld.wolfram.com/Coprime.html)
Pairs of distinct primes $(p, q)$ with $p \neq q$ form another infinite family of coprime integers. By the definition of primes, the only positive divisors of $p$ are 1 and $p$, and similarly for $q$; since $p \neq q$, the only shared [divisor](/page/Divisor) is 1, so $\gcd(p, q) = 1$.[](https://mathworld.wolfram.com/Coprime.html)
A further construction yields coprime pairs from powers of 2 and [odd](/page/Odd) integers: for $k \geq 1$ and any [odd](/page/Odd) positive integer $m$, the pair $(2^k, m)$ satisfies $\gcd(2^k, m) = 1$. This holds because the prime factorization of $2^k$ consists solely of the prime 2, while $m$ has no factor of 2, as guaranteed by the [fundamental theorem of arithmetic](/page/Fundamental_theorem_of_arithmetic), which uniquely decomposes every positive integer into a power of 2 times an [odd](/page/Odd) part.[](https://people.math.sc.edu/howard/Classes/580f/hw4.pdf)
Consecutive Fibonacci numbers provide yet another infinite family of coprime pairs: for the sequence defined by $F_1 = 1$, $F_2 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$, it follows that $\gcd(F_n, F_{n+1}) = 1$ for all $n \geq 1$. This is proven by [induction](/page/Induction): the base cases $\gcd(F_1, F_2) = \gcd(1, 1) = 1$ hold, and assuming $\gcd(F_k, F_{k+1}) = 1$, any common divisor of $F_{k+1}$ and $F_{k+2} = F_{k+1} + F_k$ would divide $F_k$, contradicting the inductive hypothesis unless the divisor is 1.[](http://web02.gonzaga.edu/faculty/axon/301/proofs-D.pdf)
Illustrative examples of coprime pairs can be found among small positive integers. The table below lists the first 10 such pairs $(a, b)$ with $1 \leq a < b \leq 20$, ordered lexicographically by increasing $a$ and then $b$:
| $a$ | $b$ |
|-----|-----|
| [1](/page/1) | 2 |
| [1](/page/1) | 3 |
| [1](/page/1) | 4 |
| [1](/page/1) | 5 |
| [1](/page/1) | 6 |
| [1](/page/1) | 7 |
| [1](/page/1) | 8 |
| [1](/page/1) | 9 |
| [1](/page/1) | 10 |
| [1](/page/1) | 11 |
These examples highlight how coprimality arises frequently, particularly with [1](/page/1) paired to any integer, since $\gcd(1, b) = 1$ for all $b$.
Coprime pairs also manifest geometrically as lattice points in the plane. The points $(m, n)$ with $m, n \in \mathbb{Z}$ and $\gcd(m, n) = 1$ are visible from the origin, meaning the line segment from $(0,0)$ to $(m, n)$ contains no other lattice points. This visualization underscores the sparsity of such points, with their density related to the probability $6/\pi^2 \approx 0.607$ that two random integers are coprime.[](https://mathworld.wolfram.com/VisiblePoint.html)
A special case drawing an analogy to integer coprimality appears in polynomials over the integers: the polynomials $x$ and $x+1$ are coprime, as $\gcd(x, x+1) = \gcd(x, (x+1) - x) = \gcd(x, 1) = 1$ via the Euclidean algorithm. Evaluating these at any integer $t$ yields the coprime pair $(t, t+1)$, linking polynomial and integer constructions.[](https://stacks.math.columbia.edu/tag/09GW)
## Applications
### In Number Theory
Coprime integers play a fundamental role in number theory, particularly through functions and theorems that quantify their distribution and properties. One key example is [Euler's totient function](/page/Euler's_totient_function), denoted $\phi(n)$, which counts the number of positive integers up to $n$ that are coprime to $n$. This function is defined for any positive integer $n$ and satisfies the formula $\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$, where the product runs over the distinct prime factors $p$ of $n$.[](https://mathworld.wolfram.com/TotientFunction.html) Additionally, via Möbius inversion, $\phi(n)$ can be expressed as $\phi(n) = \sum_{d \mid n} \mu(d) \frac{n}{d}$, where $\mu$ is the [Möbius function](/page/Möbius_function).[](https://mathworld.wolfram.com/TotientFunction.html)
Dirichlet's theorem on arithmetic progressions asserts that if $a$ and $m$ are coprime positive integers, then there are infinitely many primes congruent to $a$ modulo $m$. This result, established by Dirichlet in 1837, relies crucially on the coprimality condition to ensure the arithmetic progression contains primes, as non-coprime cases yield at most one prime.[](https://math.mit.edu/classes/18.785/2016fa/LectureNotes18.pdf) The theorem extends the understanding of prime distribution beyond the classical prime number theorem by incorporating modular constraints.
Variants of the prime number theorem incorporate coprimality in their error terms for the counting function $\pi(x; q, a)$, which denotes the number of primes up to $x$ congruent to $a$ modulo $q$. Specifically, when $\gcd(a, q) = 1$, the asymptotic $\pi(x; q, a) \sim \frac{1}{\phi(q)} \frac{x}{\log x}$ holds, with error terms analyzed through Dirichlet L-functions associated to coprime residue classes.[](https://pub.math.leidenuniv.nl/~evertsejh/ant16-7.pdf) This equidistribution among coprime classes modulo $q$ underscores the balanced spread of primes in such progressions.
Möbius inversion further highlights coprimality through the identity $\sum_{d \mid \gcd(k, n)} \mu(d) = 1$ if $\gcd(k, n) = 1$ and $0$ otherwise, serving as an indicator function for coprime pairs. This property arises from the fact that $\sum_{d \mid g} \mu(d) = [g = 1]$ for any positive integer $g$, where $[ \cdot ]$ is the Iverson bracket.[](https://mathworld.wolfram.com/MoebiusFunction.html) In broader applications, such as inverting sums over divisors, this enables the extraction of contributions solely from coprime terms in arithmetic functions.
### In Cryptography and Computing
The RSA cryptosystem, introduced in 1978, relies on the coprimality of the public encryption exponent $e$ and Euler's totient function $\phi(n)$, where $n = pq$ for distinct primes $p$ and $q$, ensuring that $e$ has a modular multiplicative inverse modulo $\phi(n)$ for decryption.[](https://people.csail.mit.edu/rivest/Rsapaper.pdf) Decryption works by computing the private exponent $d$ such that $ed \equiv 1 \pmod{\phi(n)}$, which exists precisely because $\gcd(e, \phi(n)) = 1$, allowing recovery of the plaintext via $m = c^d \mod n$ for ciphertext $c$.[](https://people.csail.mit.edu/rivest/Rsapaper.pdf)
In RSA key generation, the moduli $p$ and $q$ are chosen as distinct primes, guaranteeing $\gcd(p, q) = 1$, which enables efficient computation of $\phi(n) = (p-1)(q-1)$ and supports the security based on the difficulty of factoring $n$.[](https://people.csail.mit.edu/rivest/Rsapaper.pdf) The extended Euclidean algorithm is used to find $d$, leveraging the coprimality to compute the inverse in $O(\log n)$ time, making it practical for large keys.[](https://people.csail.mit.edu/rivest/Rsapaper.pdf)
In computing, coprime parameters enhance uniformity in pseudorandom number generators, such as linear congruential generators (LCGs) of the form $X_{n+1} = (a X_n + c) \mod m$, where full-period conditions from the Hull-Dobell theorem require $\gcd(c, m) = 1$ and $\gcd(a, m) = 1$ (among others) to ensure the sequence cycles through all residues modulo $m$. This coprimality prevents short cycles and promotes statistical uniformity, as seen in widely used LCG implementations for simulations and hashing.
In post-quantum cryptography during the 2020s, lattice-based schemes like [NTRU](/page/NTRU) use coprime polynomials to ensure invertibility in polynomial rings, such as requiring the private polynomial $f$ to be coprime with the ring modulus $x^N - 1$ modulo small primes $p$ and $q$ for computing inverses during key generation and decryption.[](https://www.ntru.org/f/hps98.pdf) This property, verified via the extended Euclidean algorithm adapted for polynomials, supports [NTRU](/page/NTRU)'s resistance to quantum attacks while maintaining efficiency, with variants like [NTRU Prime](/page/NTRU_Prime), which was evaluated as an alternate candidate in [NIST's PQC standardization process](/page/NIST_PQC_standardization_process) but not selected for standardization.[](https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization)
## Generalizations
### To Multiple Integers
The generalization of coprimality to multiple integers, specifically k-tuples where k > 2, distinguishes between mutual coprimality—where the [greatest common divisor](/page/Greatest_common_divisor) of all k integers is 1—and pairwise coprimality, where every pair among the k integers has [greatest common divisor](/page/Greatest_common_divisor) 1.[](https://www.researchgate.net/publication/232252227_The_probability_that_k_positive_integers_are_pairwise_relatively_prime) These notions differ for k > 2, as mutual coprimality permits some pairs to share common factors greater than 1, provided no single prime divides all elements. For instance, the triple (6, 15, 35) satisfies gcd(6, 15, 35) = 1 but fails pairwise coprimality since gcd(6, 15) = 3 > 1.[](https://oeis.org/wiki/Coprimality) In contrast, the triple (8, 9, 25) achieves pairwise coprimality, with gcd(8, 9) = 1, gcd(8, 25) = 1, and gcd(9, 25) = 1, and thus also mutual coprimality.[](https://www.math.brown.edu/~jhs/MA0076/IHM2020NumberTheoryUnit4.pdf) Trivial examples include (1, 1, 1), where all gcds are 1.[](https://planetcalc.com/9547/)
There exist infinitely many k-tuples of pairwise coprime positive integers for any fixed k ≥ 2; a simple [construction](/page/Construction) takes the k-th powers of the first k distinct primes, such as (2^k, 3^k, ..., p_k^k), ensuring no two share a common prime factor.[](https://www.sciencedirect.com/science/article/pii/S0022314X16300233) The Hardy-Littlewood k-tuple conjecture, which posits that admissible k-tuples of linear forms produce infinitely many simultaneous primes under certain [sieve](/page/Sieve) conditions, implies the existence of infinitely many k-tuples of distinct primes that are pairwise coprime, as distinct primes share no common factors greater than 1.
The natural density, or asymptotic probability, that k randomly selected positive integers up to n are mutually coprime approaches 1/[ζ(k)](/page/Riemann_zeta_function) as n → ∞, where [ζ](/page/Zeta) denotes the Riemann zeta function; this follows from the Euler product over primes, reflecting the independence of divisibility by distinct primes.[](https://hal.science/hal-01984389/document) For pairwise coprimality, the probability is more intricate, involving higher-order zeta values, but remains positive and bounded away from zero.[](https://www.researchgate.net/publication/232252227_The_probability_that_k_positive_integers_are_pairwise_relatively_prime)
### In Algebraic Structures
In polynomial rings, the notion of coprimality extends the integer case to elements with coefficients in $\mathbb{Z}$. Two polynomials $f, g \in \mathbb{Z}$ are said to be coprime if their greatest common divisor is a constant polynomial, meaning no non-constant polynomial divides both. This definition aligns with the Euclidean algorithm applied to polynomials, where the gcd is computed via repeated division, analogous to integers. A key result facilitating computations and irreducibility criteria is Gauss's lemma, which states that the product of two primitive polynomials (those with content 1, i.e., gcd of coefficients is 1) is primitive.[](https://www.jmilne.org/math/CourseNotes/ANT.pdf) This lemma implies that if a polynomial in $\mathbb{Z}$ factors non-trivially in $\mathbb{Q}$, then it factors similarly in $\mathbb{Z}$ after scaling, preserving coprimality properties across rings.[](https://archive.org/details/disquisitionesa00gaus)
For example, consider the polynomials $x^2 + 1$ and $x - 1$ over $\mathbb{Q}$. Applying the Euclidean algorithm, divide $x^2 + 1$ by $x - 1$: the remainder is $(1)^2 + 1 = 2$, a constant, so their gcd is 1, confirming they are coprime. Over $\mathbb{Z}$, both are primitive, and their coprimality holds since no prime divides all coefficients of a common non-constant divisor. This example illustrates how coprimality in polynomial rings detects the absence of shared irreducible factors, bridging to applications in factorization.
In the ring of Gaussian integers $\mathbb{Z} = \{a + bi \mid a, b \in \mathbb{Z}\}$, coprimality is defined using the [norm](/page/Norm) $N(\alpha) = \alpha \overline{\alpha} = a^2 + b^2$ for $\alpha = a + bi$, which is multiplicative: $N(\alpha \beta) = N(\alpha) N(\beta)$. Two Gaussian integers $\alpha, \beta$ are coprime if their gcd is a [unit](/page/Unit) (1, -1, i, or -i), equivalently if $N(\gcd(\alpha, \beta)) = [1](/page/1)$. The gcd can be computed via the [Euclidean algorithm](/page/Euclidean_algorithm), leveraging that $\mathbb{Z}$ is a [Euclidean domain](/page/Euclidean_domain) with respect to the norm. For instance, 3 and $1 + 2i$ are coprime because $N(3) = 9$ and $N(1 + 2i) = 5$ share no common prime factors in $\mathbb{Z}$, and direct computation yields gcd [1](/page/1) up to units.[](https://kconrad.math.uconn.edu/blurbs/ugradnumthy/Zinotes.pdf)
In more general algebraic structures, such as the ring of integers $\mathcal{O}_K$ of a number field $K$, coprimality is often defined for ideals rather than elements, though it extends to principal ideals generated by elements. Two ideals $\mathfrak{a}, \mathfrak{b} \subseteq \mathcal{O}_K$ are coprime if $\mathfrak{a} + \mathfrak{b} = \mathcal{O}_K$, meaning their sum is the unit ideal, or equivalently, $\mathfrak{a} \mathfrak{b} = \mathfrak{a} \cap \mathfrak{b}$. This property holds in Dedekind domains like $\mathcal{O}_K$, where every nonzero ideal factors uniquely into primes. In quadratic fields $K = \mathbb{Q}(\sqrt{d})$ for square-free integer $d$, the ring $\mathcal{O}_K$ (e.g., $\mathbb{Z}[\sqrt{d}]$ if $d \equiv 2,3 \pmod{4}$, or $\mathbb{Z}\left[\frac{1 + \sqrt{d}}{2}\right]$ otherwise) exemplifies this: prime ideals above distinct rational primes are coprime. For instance, in $\mathbb{Q}(\sqrt{-5})$, the ideals $(2, 1 + \sqrt{-5})$ and $(3, 1 + \sqrt{-5})$ are coprime since their generators generate the unit ideal. This ideal-theoretic coprimality generalizes integer coprimality, enabling unique factorization of ideals even when elements lack it.[](https://web.math.ucsb.edu/~agboola/teaching/2021/fall/225A/neukirch.pdf)
### Coprimality in Ring Ideals
In commutative algebra, two ideals $I$ and $J$ in a commutative ring $R$ with identity are defined to be coprime, or comaximal, if their sum $I + J = R$, meaning that there exist elements $a \in I$ and $b \in J$ such that $a + b = 1$.[](https://webhomes.maths.ed.ac.uk/~v1ranick/papers/atiyahmacdonald.pdf) This condition ensures that $I$ and $J$ generate the unit ideal and have no common maximal ideal containing both.[](https://webhomes.maths.ed.ac.uk/~v1ranick/papers/atiyahmacdonald.pdf) A key property of coprime ideals is that their intersection equals their product: $I \cap J = IJ$.[](https://webhomes.maths.ed.ac.uk/~v1ranick/papers/atiyahmacdonald.pdf)
In principal ideal domains (PIDs), such as the ring of integers $\mathbb{Z}$, coprimality of principal ideals $(a)$ and $(b)$ is equivalent to the coprimality of their generators, i.e., $\gcd(a, b) = 1$. This follows because in a PID, the sum of principal ideals $(a) + (b) = (\gcd(a, b))$, so the ideals sum to the unit ideal if and only if the greatest common divisor is a unit.[](https://people.tamu.edu/~yvorobets/MATH415-2021C/Lect4-07web.pdf) More generally, in Bézout rings—integral domains where every finitely generated ideal is principal—the notion of ideal coprimality aligns closely with element-wise coprimality, as the Bézout property guarantees that for coprime elements $a$ and $b$, there exist $r, s \in R$ such that $ra + sb = 1$, implying $(a) + (b) = R$.[](https://lohar.com/researchpdf/bezout_rings_and_their_subrings.pdf)
Examples illustrate this concept clearly. In $\mathbb{Z}$, the principal ideals $(2)$ and $(3)$ are coprime since $2 \cdot (-1) + 3 \cdot 1 = 1$, so $(2) + (3) = (1)$.[](https://people.tamu.edu/~yvorobets/MATH415-2021C/Lect4-07web.pdf) In the [polynomial ring](/page/Polynomial_ring) $k[x, y]$ over a [field](/page/Field) $k$, consider the principal ideals $(x)$ and $(x + 1)$; their sum is $(x) + (x + 1) = (1)$, as $1 = (x + 1) - x$, demonstrating coprimality despite the multivariable setting.[](https://math.stackexchange.com/questions/3401671/examples-of-coprime-ideals-in-mathbbcx-y-or-mathbbcx-y-z)
A significant application of coprime ideals is the [Chinese Remainder Theorem](/page/Chinese_remainder_theorem) for [ring](/page/Ring)s: if $I$ and $J$ are coprime ideals in $R$, then the natural map $R / (I \cap J) \to R/I \times R/J$ given by $r + (I \cap J) \mapsto (r + I, r + J)$ is a [ring](/page/Ring) [isomorphism](/page/Isomorphism). This generalizes the classical [theorem](/page/Theorem) for integers and extends to finite collections of pairwise coprime ideals.[](https://webhomes.maths.ed.ac.uk/~v1ranick/papers/atiyahmacdonald.pdf)