coprime

Two integers are coprime, or relatively prime, if their greatest common divisor is 1: gcd(a, b) = 1. This means they share no common positive divisors greater than 1. Equivalently, there exist integers x and y such that ax + by = 1, by Bézout's identity.

Examples illustrate the idea: gcd(8, 15) = 1, so 8 and 15 are coprime. gcd(14, 21) = 7, so they are not. Any integer is coprime with 1, and in the integer setting gcd(0, b) = |b|, so 0 is coprime with 1 or −1 but not with other numbers.

For a set of integers a1, a2, ..., an, gcd(a1, a2, ..., an) = 1 means the whole set is collectively coprime. A distinction is made between pairwise (or mutually) coprime sets, where every pair is coprime, and collectively coprime sets. Pairwise coprime implies collective coprime, but the converse is false for three or more numbers; for example gcd(6, 10, 15) = 1, yet gcd(6, 10) = 2 and gcd(10, 15) = 5.

Key properties include that if gcd(a, b) = 1, then a has a multiplicative inverse modulo b. In general, if gcd(a, b) = 1 and a divides bc, then a divides c. Coprimality also normalizes fractions: a/b is in lowest terms exactly when gcd(a, b) = 1. The totient function φ(n) counts numbers up to n that are coprime to n, reflecting a central role in number theory. Applications appear in modular arithmetic and cryptography, where choosing coprime integers ensures the existence of modular inverses and certain structural properties.