1 Definition and basic concepts

A pairwise coprime set is a set of integers in which every two distinct elements have greatest common divisor 1. This requirement is stronger than a single condition on the whole set, because it asks for coprimality to hold for each pair rather than only for the set as a whole. Such sets are commonly used in arguments where independent divisibility properties are needed.

1.1 Coprime integers

Two integers are coprime, or relatively prime, when their greatest common divisor is 1. This means they share no prime factor. The integers need not be prime themselves; for example, 8 and 15 are coprime even though both are composite.

1.2 Pairwise coprimality

A collection is pairwise coprime if every distinct pair of elements is coprime. For a set \(\{a_1, a_2, \dots, a_n\}\), this means \(\gcd(a_i, a_j)=1\) whenever \(i \neq j\). The condition is symmetric and depends only on the pairs, not on the order of the elements.

1.3 Distinction from collectively coprime sets

A set is collectively coprime, or sometimes simply coprime, if the greatest common divisor of all its elements is 1. This does not imply pairwise coprimality. For instance, the set \(\{6,10,15\}\) has total gcd 1, yet no pair among 6, 10, and 15 is coprime. Thus pairwise coprimality is a strictly stronger property.

2 Fundamental properties

Pairwise coprime sets have several useful consequences for divisibility and factorization. Their elements behave independently with respect to prime factors, which makes products and congruence conditions easier to analyze.

2.1 Greatest common divisors in the set

If a set is pairwise coprime, then the gcd of any subcollection of two or more distinct elements may still be 1, but the defining condition only concerns pairs. In particular, any prime dividing one element of the set cannot divide another. This separation of prime divisors is one of the main structural features of such sets.

2.2 Prime factorization interpretation

Each integer in a pairwise coprime set has a prime factorization that uses primes not appearing in any other element of the set. The same prime may appear with higher exponent inside a single element, but it cannot occur in two different elements. This interpretation is often the easiest way to check pairwise coprimality for small examples.

2.3 Product and divisor relationships

If \(a_1, a_2, \dots, a_n\) are pairwise coprime, then each \(a_i\) divides the product \(a_1a_2\cdots a_n\) in a particularly independent way. More generally, the least common multiple of the set is the product of the elements when all are positive and pairwise coprime. This property is central in arguments involving divisibility and modular arithmetic.

3 Examples and non-examples

Examples help distinguish pairwise coprime sets from sets that only satisfy a weaker global gcd condition. Many standard constructions arise from primes, prime powers, or carefully chosen composite numbers.

3.1 Finite pairwise coprime sets

Simple finite examples include \(\{2,3,5\}\), \(\{8,9,25\}\), and \(\{14,15,16\}\). In each case, every pair of numbers has gcd 1. Sets built from distinct primes or powers of distinct primes are especially common examples.

3.2 Infinite families of pairwise coprime integers

There are infinite pairwise coprime families, such as the sequence of all prime numbers. Another classical example is \(\{n!+1 : n \ge 1\}\) in certain contexts, though the numbers themselves need not all be pairwise coprime. A more direct infinite family is given by distinct prime powers with different underlying primes.

3.3 Sets that are coprime but not pairwise coprime

The set \(\{6,10,15\}\) is a standard non-example. Its total gcd is 1, yet \(\gcd(6,10)=2\), \(\gcd(6,15)=3\), and \(\gcd(10,15)=5\). Such examples show that a global gcd condition does not control pairwise interactions.

4 Construction methods

Several common techniques produce pairwise coprime sets. These methods are useful in proofs and in designing examples with controlled divisibility behavior.

4.1 Using distinct prime powers

A straightforward construction is to choose numbers of the form \(p_1^{e_1}, p_2^{e_2}, \dots, p_n^{e_n}\) where the primes \(p_i\) are all distinct. Since each number has prime factors disjoint from the others, the set is pairwise coprime. This method is flexible because the exponents may be chosen freely.

4.2 Recursive constructions

Pairwise coprime sets can also be built recursively. Starting from a set with product \(P\), one may choose a new integer of the form \(P k + 1\), which is automatically coprime to every previous element. Repeating this process yields a growing family in which each new term avoids all earlier prime factors.

4.3 Sets formed from modular constraints

Some constructions arise by solving congruences so that each new element avoids divisibility by the primes already present. For example, one may select numbers congruent to 1 modulo the product of earlier terms. This ensures no common divisor greater than 1 can occur with any earlier member, making the set pairwise coprime.

Pairwise coprime sets are closely tied to classical results in elementary number theory. They often appear in proofs that use induction, prime factor arguments, or modular decomposition.

5.1 Euclid-style arguments

Euclid-type reasoning shows that given any finite pairwise coprime set, one can construct another integer coprime to all of them by taking the product and adding 1. If \(N=a_1a_2\cdots a_n+1\), then \(N\) shares no common prime factor with any \(a_i\). This argument is a standard source of new coprime numbers.

5.2 Applications of the Chinese remainder theorem

The Chinese remainder theorem applies naturally when moduli are pairwise coprime. It guarantees the existence of a simultaneous solution to a system of congruences with such moduli, and that solution is unique modulo the product of the moduli. Pairwise coprime sets therefore provide the basic framework for many congruence constructions.

5.3 Bounds on pairwise coprime subsets

In finite sets of integers, pairwise coprime subsets may be studied through bounds on their size or on the size of their product. Since each prime factor can appear in only one element, such sets are constrained by the distribution of prime divisors. These bounds are often used in combinatorial number theory and divisor-counting arguments.

6 Computational aspects

Checking pairwise coprimality is algorithmically straightforward, though the cost depends on the size of the numbers and the number of elements in the set. Practical methods rely on repeated greatest common divisor computations.

6.1 Testing pairwise coprimality

To test whether a set is pairwise coprime, compute the gcd of every distinct pair. If all pairwise gcds equal 1, the set satisfies the condition. For a set of \(n\) integers, this requires examining \(\binom{n}{2}\) pairs.

6.2 Algorithms using gcd computations

The Euclidean algorithm is the standard tool for gcd calculations. Because it is efficient, pairwise coprimality can usually be checked quickly even for large integers. In practice, one may also factor numbers when repeated tests are needed, but direct gcd evaluation is often simpler.

6.3 Complexity considerations

The naive pairwise check grows quadratically with the number of elements. For large data sets, this can become expensive, especially when the integers themselves are large. Still, the efficiency of gcd algorithms makes the approach practical in many applications, and early termination is possible as soon as one non-coprime pair is found.

7 Applications in number theory

Pairwise coprime sets are widely used because they simplify the behavior of products, congruences, and divisibility conditions. Their independence properties make them valuable in both proofs and constructions.

7.1 Divisibility proofs

When numbers are pairwise coprime, divisibility by one element rarely interacts with divisibility by another. This allows proofs to separate cases cleanly and to infer, for example, that if a product is divisible by each member of the set, then each factor may be handled independently. Such reasoning appears frequently in elementary number theory.

7.2 Congruence systems

Systems of congruences with pairwise coprime moduli are especially manageable. The Chinese remainder theorem gives a unique simultaneous solution modulo the product of the moduli. As a result, pairwise coprime sets provide a standard setting for constructing integers with prescribed residues.

7.3 Diophantine equations

Pairwise coprimality often helps reduce Diophantine equations by separating factors. If a product of pairwise coprime integers equals another integer or a power, one can frequently deduce divisibility properties for each factor individually. This can simplify factorization arguments and lead to parametrizations of solutions.

Several closely related notions appear in discussions of coprimality. The differences are mostly about whether the condition is pairwise, collective, or tied to a particular algebraic context.

8.1 Mutually coprime sets

Mutually coprime is another term often used for pairwise coprime. In many texts, the phrases are interchangeable. Both indicate that every pair of distinct elements has gcd 1.

8.2 Relatively prime numbers

Two relatively prime numbers are numbers whose gcd is 1. This is the pairwise condition applied to a single pair. The concept is fundamental and serves as the building block for larger pairwise coprime collections.

8.3 Pairwise relatively prime collections

A pairwise relatively prime collection is simply a set or list in which every distinct pair is relatively prime. The term emphasizes the element-by-element nature of the property and is common in discussions of modular arithmetic and factorization.