Understanding Relatively Prime Numbers
Two integers are relatively prime if their greatest common divisor (GCD) equals 1. Crucially, relatively prime numbers need not be prime themselves. For instance, 14 and 15 are both composite: 14 = 2 × 7 with factors {1, 2, 7, 14}, and 15 = 3 × 5 with factors {1, 3, 5, 15}. Their only shared factor is 1, making them coprime.
The terminology reflects this relationship: if a and b are coprime, we say a is prime to b. This differs from saying a is a prime number, which has a different meaning entirely.
Checking Pairwise and Setwise Coprimality
When examining multiple numbers, two distinct concepts apply:
- Setwise coprime: A set has GCD equal to 1. For example, {4, 6, 21} is setwise coprime because GCD(4, 6, 21) = 1, even though 4 and 6 share the factor 2.
- Pairwise coprime: Every possible pair within the set is coprime. The set {4, 7, 27} satisfies this: (4,7), (4,27), and (7,27) are all coprime pairs.
Pairwise coprimality is the stricter condition and implies setwise coprimality.
Testing Coprimality
The primary method involves prime factorization. Factorize each number completely, then inspect their prime factor lists. If no prime factor appears in more than one number, they are coprime.
GCD(a, b) = 1 ⟺ a and b are coprime
a, b— Two integers to test for coprimalityGCD(a, b)— Greatest common divisor; equals 1 for coprime numbers
Practical Example: Testing 42 and 75
Factorize 42: 42 = 2 × 3 × 7
Factorize 75: 75 = 3 × 5²
Both share the prime factor 3, so their GCD is at least 3. Therefore, 42 and 75 are not relatively prime. This method scales to any number of integers: if all prime factors appear in only one number, the set is coprime.
Common Pitfalls and Key Facts
Avoid these misconceptions when working with coprime numbers:
- Even numbers cannot be pairwise coprime — All even numbers share 2 as a factor. For a pair to be coprime, at least one must be odd. Sets like {2, 4, 8} are not coprime because every element is divisible by 2.
- 1 is coprime with everything — The number 1 has only itself as a factor. By definition, GCD(1, n) = 1 for any positive integer n, making 1 coprime with all other integers.
- Composite numbers can be coprime — Coprimality is about shared factors, not primality. Two composite numbers like 9 and 25 (both non-prime) are coprime because they share no prime factors.
- Setwise and pairwise coprimality differ — A set can be setwise coprime without being pairwise coprime. Always clarify which type you need: do all pairs require GCD = 1, or just the entire set?