What Does Relatively Prime Mean?
Two integers are said to be relatively prime (or coprime) if their greatest common divisor (GCD) is 1. In other words, they share no common positive factors other than 1. For example, 8 and 15 are relatively prime because no number greater than 1 divides both evenly.
The Euclidean Algorithm
The Euclidean algorithm is an efficient method for computing the GCD of two numbers. It works by repeatedly replacing the larger number with the remainder when the larger is divided by the smaller, until the remainder is zero. The last non-zero remainder is the GCD.
Algorithm Steps
Divide a by b, get remainder r. Replace a with b, b with r. Repeat until r = 0.
GCD(a, b) = GCD(b, a mod b)
Coprime Condition
If the Euclidean algorithm yields GCD = 1, the numbers are coprime.
GCD(a, b) = 1 => Coprime
Example: GCD(48, 18)
48 = 2 x 18 + 12, 18 = 1 x 12 + 6, 12 = 2 x 6 + 0. GCD = 6.
GCD(48, 18) = 6 (not coprime)
Properties of Coprime Numbers
- Any two consecutive integers are always coprime.
- Any prime number is coprime with any number it does not divide.
- 1 is coprime to every integer.
- If a and b are coprime, then a x b = LCM(a, b).
Applications
- RSA encryption relies on choosing two large coprime numbers.
- Simplifying fractions: a fraction a/b is in lowest terms when GCD(a, b) = 1.
- The Chinese Remainder Theorem requires pairwise coprime moduli.
- Gear ratios in engineering use coprime tooth counts to distribute wear evenly.