1 Definition and basic concepts

Coprimality is the property shared by integers whose only positive common divisor is 1. In elementary number theory, it provides a way to measure how independent two numbers are with respect to divisibility. The concept is also commonly expressed through the greatest common divisor, which gives a precise test for whether two values are coprime.

1.1 Greatest common divisor

The greatest common divisor, often abbreviated gcd, of two integers is the largest positive integer dividing both of them. Two integers are coprime exactly when their gcd equals 1. This criterion is useful because it turns a qualitative statement about shared factors into a computable quantity.

1.2 Relatively prime integers

Two integers are called relatively prime, or coprime, when they have no common divisor greater than 1. The term does not require either number to be prime. For example, 8 and 15 are coprime even though both are composite, since their only common divisor is 1.

1.3 Pairwise coprime sets

A set of integers is pairwise coprime if every two distinct members of the set are coprime. This is stronger than requiring the entire set to have no common divisor larger than 1. For instance, the numbers 6, 35, and 13 are pairwise coprime, while 6, 10, and 15 are not.

1.4 Basic examples and non-examples

Examples of coprime pairs include 3 and 10, 7 and 20, and 14 and 15. Non-examples include 6 and 9, which share the factor 3, and 12 and 18, which share several divisors. The distinction is determined entirely by common factors, not by size, parity, or whether the numbers are prime.

2 Fundamental properties

Coprimality interacts closely with divisibility and factorization. Many basic results in arithmetic can be expressed by translating coprimality into statements about prime factors, products, and algorithms for computing gcd values.

2.1 Divisibility criteria

If a number divides two integers, then it also divides any linear combination of them. This observation is often used to test coprimality: if integers a and b share a common divisor d, then d divides every combination ma + nb. Conversely, if one can find integers m and n such that ma + nb = 1, then a and b must be coprime.

2.2 Prime factorization characterization

Two integers are coprime precisely when their prime factorizations have no prime in common. If one number is written as a product of prime powers and the other as a product of different prime powers, then the absence of overlapping primes implies gcd 1. This makes coprimality a direct consequence of the uniqueness of prime factorization.

2.3 Behavior under multiplication

Coprimality often behaves predictably under products, although the details depend on whether factors are already coprime to one another. These rules are widely used in arithmetic proofs and in computations involving factorization.

2.3.1 Coprimality of products

If a number is coprime to each of two other numbers that are themselves coprime, then it is also coprime to their product. More generally, if gcd(a, b) = 1 and gcd(a, c) = 1, then gcd(a, bc) = 1. This property allows coprimality to be extended from individual factors to whole products.

2.3.2 Common factors in powers

When two numbers are coprime, all positive powers of one remain coprime to the other. Thus, if gcd(a, b) = 1, then gcd(a^m, b^n) = 1 for any positive integers m and n. Shared factors cannot appear through exponentiation if they were absent from the original numbers.

2.4 Euclidean algorithm and coprimality

The Euclidean algorithm computes the gcd of two integers by repeated division with remainder. It is one of the most efficient ways to determine coprimality in practice. If the algorithm ends with remainder 1, then the numbers are coprime. Its recursive structure also underlies the extended Euclidean algorithm, which produces coefficients expressing the gcd as a linear combination.

3 Coprimality in modular arithmetic

Coprimality plays a central role in modular arithmetic, especially in questions of invertibility and congruences. Many standard results in congruence theory depend on whether an integer is coprime to the modulus.

3.1 Invertible residues

A residue class modulo n is invertible if it has a multiplicative inverse modulo n. This happens exactly when the representative integer is coprime to n. The set of all invertible residues modulo n forms a multiplicative structure that is fundamental in number theory.

3.2 Congruences and inverses

If a is coprime to n, then the congruence ax ≡ 1 mod n has a solution. Such an x is called a modular inverse of a modulo n. Coprimality therefore determines whether division by a is possible in modular arithmetic, at least in the sense of multiplying by an inverse.

3.3 Chinese remainder theorem

The Chinese remainder theorem describes how simultaneous congruences can be solved when moduli are pairwise coprime. In that setting, a system of congruences has a unique solution modulo the product of the moduli. Coprimality ensures that separate modular conditions combine cleanly without interference.

3.4 Reduced residue systems

A reduced residue system modulo n is a complete set of representatives of the invertible residue classes modulo n. Its size is given by Euler's totient function. Such systems are built from integers coprime to n and are used to organize modular arithmetic in a structured way.

4 Counting and distribution

Coprimality can be studied statistically by counting how often integers are relatively prime. These questions lead to classical arithmetic functions and asymptotic formulas describing the distribution of coprime pairs and tuples.

4.1 Euler's totient function

Euler's totient function counts the positive integers up to n that are coprime to n. It is one of the most important arithmetic functions in number theory. Its values reflect the prime factorization of n and measure the number of invertible residues modulo n.

4.2 Probability that integers are coprime

The probability that two randomly chosen positive integers are coprime is a famous result in analytic number theory. This probability is equal to 6 divided by pi squared. More generally, the chance that several integers are mutually coprime can be described by analogous zeta-function formulas.

4.3 Counting coprime pairs

Counting the number of coprime pairs in a region of the integer lattice reveals the average behavior of gcd values. Such counts are often approximated using summatory versions of the totient function or by inclusion-exclusion arguments. They connect local divisibility conditions with global density estimates.

4.4 Coprime tuples and density

For triples and higher tuples of integers, one can ask for the proportion that are jointly coprime or pairwise coprime. These densities depend on the number of coordinates and are naturally expressed as infinite products over primes. The resulting formulas generalize the two-variable case and show that coprimality remains common even in higher dimensions.

Several arithmetic functions are built from gcd relations and coprimality conditions. These functions are valuable because they package large families of counting problems into compact algebraic expressions.

5.1 Möbius function

The Möbius function assigns values according to the prime factorization of an integer. It is especially important in inversion formulas and in detecting squarefree numbers. Because it is tied to divisibility by primes, it often appears in counts of coprime integers.

5.2 Jordan totient function

The Jordan totient function generalizes Euler's totient function to higher dimensions. It counts tuples of integers with certain coprimality restrictions relative to a modulus. This makes it a natural extension of the totient concept from single integers to multi-variable settings.

5.3 Arithmetic functions involving gcd

Many arithmetic functions depend directly on the gcd of their arguments. Examples include functions that count common divisors or weight pairs by their greatest common divisor. These functions frequently appear in summation identities and multiplicative formulas.

5.4 Inclusion-exclusion methods

Inclusion-exclusion is a standard technique for counting objects that satisfy coprimality conditions. By subtracting and restoring overlaps among divisibility constraints, it converts a difficult counting problem into a manageable sum over prime factors. This method is central to deriving formulas involving totients, Möbius inversion, and densities.

6 Applications

Coprimality has both theoretical and practical uses. It appears in the reduction of fractions, the solution of equations in integers, and computational procedures that rely on modular inverses.

6.1 Rational numbers in lowest terms

A rational number is in lowest terms when its numerator and denominator are coprime. This condition guarantees that the fraction cannot be simplified further. It also ensures uniqueness of representation up to sign, making coprimality essential in the standard form of rational numbers.

6.2 Cryptography and modular inverses

Many cryptographic methods rely on arithmetic modulo large integers, where invertibility depends on coprimality. Modular inverses are needed for encoding, decoding, and key-related computations. The efficiency of these methods often depends on fast algorithms for gcd and modular arithmetic.

6.3 Diophantine equations

Linear Diophantine equations often have integer solutions only when certain coefficients are coprime. For example, equations of the form ax + by = c are solvable precisely when the gcd of a and b divides c. Coprimality therefore acts as a solvability condition in integer equation problems.

6.4 Lattice point counting

Coprime lattice points are integer points whose coordinates have gcd 1. Counting such points inside geometric regions is a common problem in analytic and geometric number theory. These counts reveal how arithmetic conditions influence the distribution of points in the plane and in higher-dimensional lattices.

7 Generalizations and variants

The idea of coprimality extends beyond ordinary integers. Similar notions apply to collections of integers, polynomial rings, ideals, and other algebraic systems where divisibility can be defined.

7.1 Mutual coprimality

A collection of objects is mutually coprime when every pair has gcd 1, or, in a broader sense, when they share no common nontrivial divisor collectively. The exact meaning depends on context. In integer settings, mutual coprimality often supports factorization and decomposition arguments.

7.2 Coprimality in polynomial rings

Polynomials over a field can be coprime if they share no nonconstant common factor. The role of the gcd is played by a polynomial greatest common divisor. Many results from integer arithmetic have direct analogues for polynomials, including versions of the Euclidean algorithm and Bézout-type identities.

7.3 Coprime ideals

In abstract algebra, two ideals may be called coprime if their sum is the entire ring. This notion generalizes the integer condition gcd 1 to ring theory. It is particularly useful in the study of quotient structures and in general forms of the Chinese remainder theorem.

7.4 Coprimality in abstract algebra

Coprimality appears throughout algebra wherever a notion of divisibility exists. It can describe relationships among elements, ideals, or substructures that have no nontrivial overlap. This broad perspective shows that coprimality is not merely a property of integers, but a general principle about independence under factorization.

</INTERNAL_LINK_CANDIDATES> Greatest common divisor (largest positive integer dividing two integers) Euler's totient function (count of integers up to n that are coprime to n) Euclidean algorithm (procedure for computing the gcd) Extended Euclidean algorithm (algorithm that also finds Bézout coefficients) Prime factorization (expression of an integer as primes raised to powers) Modular inverse (number that multiplies to 1 modulo n) Chinese remainder theorem (result solving compatible congruences for coprime moduli) Reduced residue system (set of invertible residues modulo n) Möbius function (arithmetic function used in inversion and squarefree tests) Jordan totient function (generalization of the totient to tuples) Inclusion-exclusion principle (counting method for overlapping conditions) Diophantine equation (equation seeking integer solutions) Lattice point (integer-coordinate point in space) Coprime ideals (ideals whose sum is the whole ring) Polynomial ring (ring of polynomials with algebraic division notions) Bézout identity (expression of gcd as a linear combination) Invertible residue (modular class with a multiplicative inverse) Squarefree number (integer not divisible by any square greater than 1) Linear combination (sum of multiples of given integers) Rational number in lowest terms (fraction whose numerator and denominator are coprime) </INTERNAL_LINK_CANDIDATES>