relatively prime

Two numbers are relatively prime when they have nothing in common factor-wise — like two gears with no shared tooth count, they only line up again after a full cycle. The numbers themselves need not be prime; 8 and 9 share no factor beyond 1, even though neither is a prime.

Formally, integers a and b are relatively prime (also called coprime) when their greatest common divisor is 1: gcd(a, b) = 1. That means the only positive integer dividing both is 1. So 14 and 15 are coprime, while 14 and 21 are not, since they share the factor 7.

This condition is the quiet hinge of many results. A fraction is in lowest terms exactly when its numerator and denominator are coprime. A residue a has a multiplicative inverse modulo n exactly when a and n are coprime. And being pairwise coprime is the hypothesis that makes the Chinese Remainder Theorem combine separate congruences cleanly. One caution: three numbers can be coprime as a whole group (gcd of all three is 1) without being coprime in pairs — 6, 10, 15 is such a trio.