By Lee Johnson Updated Aug 30, 2022
Sky_Blue/iStock/GettyImages
In mathematics, the concept of coprimality—also called relatively or mutually prime—helps us understand how numbers interact based on their prime factors. A pair of integers is coprime when the only common divisor they share is 1. This property underlies many areas of number theory, cryptography, and algorithm design.
Two numbers are coprime if, after decomposing each into its prime factors, no prime appears in both factorizations. For instance, 21 = 3 × 7 and 22 = 2 × 11; the only shared divisor is 1, so 21 and 22 are coprime. Prime numbers are automatically coprime with any number that does not contain that prime in its factorization.
Determining coprime status begins with prime factorization. Take 35 as an example:
• 35 ÷ 5 = 7 (both primes) → 35 = 5 × 7.
Next, factor 60:
• 60 ÷ 2 = 30 → 30 ÷ 2 = 15 → 15 ÷ 3 = 5 → 5 is prime, so 60 = 2² × 3 × 5.
By listing the prime factors, we can see which primes are absent and therefore suitable for constructing coprimes.
Once the prime factors of a number are known, any integer built solely from primes not present in that factorization will be coprime to it. For 35 (primes 5 and 7), numbers such as 2, 3, 11, 13, 17, 19, 23, 29, 31, 37, etc., and their products—6 (2×3), 9 (3²), 22 (2×11), 33 (3×11), 26 (2×13)—are all coprime to 35.
Similarly, for 60 (primes 2, 3, 5), any integer that avoids these primes is coprime. Examples include 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, and their products: 77 (7×11), 91 (7×13), 119 (7×17), 143 (11×13), etc.
Useful shortcuts:
The simplest verification is to factor both numbers and look for shared primes. Alternatively, compute the GCD; if it equals 1, the numbers are coprime. This approach is faster for large integers and is the basis for many cryptographic protocols.
Online prime factorization and GCD calculators can automate these steps. Trusted resources include WolframAlpha, the Number Theory Toolbox, and other reputable mathematics platforms.
