Relatively Prime Integers
What you'll learn: You'll discover what it means for two integers to be relatively prime and why this relationship unlocks special divisibility properties.
Core Idea
Two integers are called relatively prime (or coprime) if their greatest common divisor (GCD) is exactly 1. In other words, they share no common divisors other than 1 itself.
For example:
- 8 and 15 are relatively prime because GCD(8, 15) = 1
- 12 and 18 are not relatively prime because GCD(12, 18) = 6
Notice that relatively prime integers don't have to be prime numbers themselves! The number 8 = 2³ is composite, yet 8 and 15 are relatively prime.
Why This Matters
When GCD(a, b) = 1, several powerful properties emerge:
Bézout's Identity becomes especially clean: There exist integers x and y such that ax + by = 1. This means you can "build" the number 1 using linear combinations of a and b.
Unique divisibility: If a relatively prime pair both divide some number n, then their product must also divide n. For instance, if 8|n and 15|n, then 120|n automatically.
Cancelation works: If a·c ≡ b·c (mod n) and GCD(c, n) = 1, you can safely cancel c from both sides.
Checking Relatively Prime Status
Use the Euclidean Algorithm to find GCD(a, b). If the result is 1, the integers are relatively prime. For instance, checking 21 and 32: the algorithm quickly yields GCD(21, 32) = 1, confirming they're relatively prime.
Key Takeaway: Two integers are relatively prime when GCD = 1, which grants them special algebraic properties that make calculations and proofs significantly simpler in number theory.