1 Definition and basic concepts
Coprime integers are integers whose greatest common divisor is 1. This means they have no shared positive factor other than 1. The idea applies to two integers as well as to larger collections, and it is one of the basic organizing principles in elementary number theory.
Coprimality is often described using the phrase relatively prime. The two expressions are usually interchangeable in ordinary mathematical usage, although coprime sometimes suggests a direct focus on the shared factor structure of the numbers involved.
1.1 Greatest common divisor
The greatest common divisor of two integers is the largest integer that divides both of them. When this divisor equals 1, the integers are coprime. For example, 8 and 15 are coprime because their only common divisor is 1.
The greatest common divisor provides a standard way to measure how much factor structure two integers share. If the gcd is greater than 1, then the numbers have at least one nontrivial common factor.
1.2 Relatively prime numbers
Two numbers are relatively prime if they are coprime. The terminology does not require either number to be prime. For instance, 9 and 28 are relatively prime even though both are composite.
In many contexts, the term is used to emphasize a relationship between two integers rather than an intrinsic property of either number alone. The definition depends only on their shared divisors.
1.3 Pairwise coprime and mutually coprime sets
A set of integers is pairwise coprime if every distinct pair in the set is coprime. A set is sometimes called mutually coprime in the broader sense that all elements share no common factor greater than 1 when considered together.
These notions are not identical. A collection may have overall gcd 1 while still containing pairs that are not coprime. For example, 6, 10, and 15 have greatest common divisor 1 as a set, but no pair among them is coprime.
1.4 Equivalent characterizations
Coprimality can be expressed in several equivalent ways. These characterizations are useful in proofs because they connect divisibility, prime factorization, and linear combinations.
1.4.1 No common prime factors
Two integers are coprime exactly when they share no prime factor. If a prime divides both numbers, then their gcd is at least that prime, so they cannot be coprime.
This viewpoint is often the most intuitive, since every integer can be built from prime factors. Coprimality then means that the prime factor lists of the numbers do not overlap.
1.4.2 Bézout's identity
Two integers are coprime if and only if there exist integers x and y such that ax + by = 1. This statement is known as Bézout's identity.
It is one of the most powerful criteria for coprimality. It shows that a greatest common divisor of 1 is equivalent to being able to express 1 as an integer linear combination of the two numbers.
1.4.3 Products and divisibility criteria
If a number divides a product and is coprime to one factor, then it must divide the other factor. This is a standard divisibility principle that follows from Bézout's identity.
More generally, coprimality often allows factors to be “canceled” in divisibility arguments. Such rules are central in elementary proofs involving congruences and factorization.
2 Properties of coprime integers
Coprimality has several stable properties under common arithmetic operations. These properties make it especially useful for simplifying arguments about divisibility and factor structure.
2.1 Symmetry and basic consequences
Coprimality is symmetric: if a is coprime to b, then b is coprime to a. It also holds for signed integers, since changing the sign of a number does not alter its divisors.
If two numbers are coprime, then any common divisor of one of them with a third number must be handled carefully in calculations. Many standard proofs rely on the fact that a common divisor of both numbers would contradict the gcd being 1.
2.2 Coprimality under multiplication
If a is coprime to b and also coprime to c, then a is coprime to bc, provided the relevant conditions are satisfied. Similarly, if a is coprime to a product, then it is coprime to each factor of that product.
This behavior is closely tied to prime factors. A prime dividing both a and bc must divide one of the factors of bc, which lets coprimality be tested through the structure of products.
2.3 Coprimality and prime factorization
Prime factorization gives a complete description of coprimality. Two integers are coprime precisely when their prime factorizations have no prime in common.
This makes prime decomposition a natural tool for checking whether a pair of numbers is relatively prime. It also helps explain why coprime integers often behave independently in formulas involving multiplication.
2.4 Coprimality in arithmetic progressions
Certain families of integers have predictable coprimality properties. Arithmetic progressions often produce terms with shared factor patterns, but special cases show strong independence.
2.4.1 Consecutive integers
Any two consecutive integers are coprime. Since one of them is even and the other is odd, they cannot share a factor greater than 1.
More generally, consecutive integers differ by 1, so any common divisor must divide 1. That forces the gcd to be 1.
2.4.2 Powers and exponents
If a and b are coprime, then their positive powers are also coprime. Raising numbers to powers does not create new shared prime factors.
This property is useful in algebraic manipulation, especially when working with exponentiation in divisibility arguments and modular arithmetic.
2.4.3 Preservation under reduction
If two integers are coprime, dividing both by a common factor is not possible, but reducing one number modulo the other can preserve useful coprimality relations. For example, if a is coprime to b, then a and a multiple of b plus or minus a remain closely related in gcd computations.
This principle appears frequently in the Euclidean algorithm, where replacing one number by a remainder does not change the gcd.
3 Coprime integers in modular arithmetic
Coprimality plays a central role in modular arithmetic because invertibility modulo n depends exactly on being coprime to n. This connection links divisibility with congruence relations.
3.1 Invertible residues modulo n
A residue class modulo n is invertible if it has a multiplicative inverse. The residue represented by a is invertible modulo n precisely when gcd(a, n) = 1.
This criterion identifies which numbers can be “divided by” modulo n. If a and n share a nontrivial factor, then a cannot be inverted modulo n.
3.2 Multiplicative inverses
When a and n are coprime, there exists an integer b such that ab is congruent to 1 modulo n. The integer b is a multiplicative inverse of a modulo n.
These inverses are fundamental in solving congruences. They allow equations like ax ≡ c mod n to be rewritten in a simpler form when a is coprime to n.
3.3 Reduced residue systems
A reduced residue system modulo n is a set of integers representing all invertible residues modulo n. Its elements are exactly the integers between 1 and n that are coprime to n.
Such systems are used to study the multiplicative structure of integers modulo n. They capture the numbers that behave like units under multiplication modulo n.
3.4 Euler's theorem
Euler's theorem states that if a and n are coprime, then a raised to the power φ(n) is congruent to 1 modulo n, where φ(n) is Euler's totient function. This theorem generalizes a familiar phenomenon from prime moduli.
It is one of the most important results connecting coprimality and exponentiation in modular arithmetic. It also underlies many algorithms and proofs in elementary and computational number theory.
3.4.1 Euler's totient function
Euler's totient function φ(n) counts the positive integers less than or equal to n that are coprime to n. It measures the size of the reduced residue system modulo n.
The function is multiplicative in a suitable sense and depends strongly on the prime factorization of n. Because it counts coprime integers, it is one of the main arithmetic functions associated with coprimality.
3.4.2 Applications to congruences
Euler's theorem can be used to simplify high powers modulo n when the base is coprime to n. This is especially useful in computations where direct exponentiation would be impractical.
It also provides a theoretical foundation for solving and transforming congruences, particularly when an inverse modulo n exists.
4 Fractions and rational numbers
Coprime integers are central to the theory of fractions because every rational number can be written in lowest terms using coprime numerator and denominator. This gives a canonical form for rational numbers.
4.1 Lowest terms
A fraction is in lowest terms when its numerator and denominator are coprime. In that case, no further reduction by a common factor is possible.
Writing a fraction in lowest terms is a standard normalization step. It makes comparisons and algebraic manipulations more transparent.
4.2 Simplification by common factors
If the numerator and denominator of a fraction share a factor, the fraction can be simplified by dividing both by that factor. Repeating this process eventually produces a fraction in lowest terms.
This procedure reflects the role of the gcd as the maximal removable common factor. It is one of the first practical uses of coprimality in arithmetic.
4.3 Uniqueness of reduced fractions
Every rational number has a unique representation in lowest terms, up to the sign convention used for the denominator. This uniqueness depends on the fact that the numerator and denominator are coprime.
Because the reduced form is canonical, it provides a reliable way to represent rational numbers and compare them without ambiguity.
4.4 Coprime numerators and denominators
In a reduced fraction, the numerator and denominator share no common prime factor. This implies that their arithmetic properties are relatively independent.
The coprimality of numerator and denominator is also essential in many number-theoretic arguments involving rational solutions, divisibility, and simplification.
5 Methods for determining coprimality
Several standard methods are used to test whether two integers are coprime. Some are theoretical, while others are practical for computation.
5.1 Euclidean algorithm
The Euclidean algorithm computes the greatest common divisor by repeated division with remainder. If the algorithm ends with 1, then the numbers are coprime.
This method is efficient and works well for large integers. It is the most common algorithmic test for coprimality in practice.
5.2 Prime factorization method
If the prime factorization of each number is known, coprimality can be checked by comparing their prime factors. If no prime appears in both factorizations, the numbers are coprime.
Although conceptually simple, this approach can be less efficient than the Euclidean algorithm when the numbers are large and factorization is difficult.
5.3 Using divisibility tests
Simple divisibility tests can sometimes show that two numbers are not coprime, especially when a small prime divides both. If such a shared factor is found, the pair is immediately ruled out.
Conversely, proving coprimality by divisibility tests alone is often incomplete unless all possible common prime factors are excluded. These tests are therefore mainly used as quick checks.
5.4 Computational approaches
In computing, gcd routines are used to determine coprimality automatically. Modern implementations often combine the Euclidean algorithm with optimized arithmetic methods for speed.
These approaches are important in cryptography, symbolic computation, and algorithms that require modular inverses or fraction reduction. Coprimality checks are usually built into larger computational systems.
6 Advanced topics
Coprimality appears in deeper mathematical constructions where the independence of factors is essential. It often serves as a condition that allows separate pieces of an argument to be recombined cleanly.
6.1 Pairwise coprimality in number theoretic constructions
Pairwise coprime sets are useful in constructing examples with controlled divisibility behavior. Because each pair shares no factor, the numbers interact in a highly structured way.
Such sets appear in problems involving least common multiples, congruences, and factorization patterns. They are also used to build examples where separate modular conditions can be handled independently.
6.2 Chinese remainder theorem
The Chinese remainder theorem describes when a system of congruences can be solved simultaneously. A key hypothesis is that the moduli are pairwise coprime.
When the moduli are pairwise coprime, congruences modulo each modulus combine into a unique solution modulo their product. This makes coprimality a structural condition for decomposition and reconstruction in modular arithmetic.
6.3 Coprimality in Diophantine equations
In Diophantine equations, coprime conditions often help reduce the search for integer solutions. If two quantities are coprime, divisibility constraints can force strong conclusions about factors.
Many classical arguments begin by assuming a solution is written in lowest terms. The coprimality of numerator and denominator or of parameter pairs then helps rule out impossible cases or identify structural patterns.
6.4 Applications in algebraic number theory
In algebraic number theory, ideas analogous to coprimality appear in the study of ideals and factorization in number fields. The basic intuition remains the same: objects are considered independent when they share no nontrivial common divisor.
These generalizations preserve the role of coprimality as a tool for organizing divisibility, decomposition, and arithmetic relations in more abstract settings.