Coprime Calculator
Check if two numbers are coprime (share no common factors other than 1). See their greatest common factor, least common multiple, and step-by-step division work.
Their greatest common divisor is 1. They share no common positive divisors other than 1.
Step-by-Step Division Work (Euclidean Method)
Finding the remainder1. What Does It Mean to Be Coprime?
Two numbers are coprime (or relatively prime) if their greatest common factor is 1. Put simply, they don't share any whole number factors other than 1.
The numbers don't need to be prime themselves! For example, 8 and 9 are both composite numbers (8 = 2 × 2 × 2 and 9 = 3 × 3). But because they share no prime building blocks in common, they are coprime with each other.
Compare Prime Factors
Factor InspectorPick any two numbers to see their prime factors and check if they share any:
2. The Combination Rule (Bézout's Identity)
A neat mathematical rule discovered by Étienne Bézout shows that you can always multiply two numbers (a and b) by whole numbers (x and y) so their sum equals their greatest common factor:
When two numbers are coprime, their greatest common factor is 1, so: (a × x) + (b × y) = 1. This formula is the secret engine behind modern online encryption (like creating decryption keys for secure HTTPS connections).
Bézout Equation Step Solver
a·x + b·y = 1Enter any two numbers to find the multipliers (x and y) that combine them to equal their GCF:
3. Coprime & Common Factor Reference Table
20 interesting number pairs to explore. Click any row to test it in the calculator above:
| Pair (a, b) | Type | GCF | Coprime? | Why? | Try It |
|---|---|---|---|---|---|
| (8, 9) | Consecutive Numbers | 1 | Yes | 2³ and 3² share no factors | |
| (14, 25) | Composite Pair | 1 | Yes | (2 × 7) and 5² share no factors | |
| (12, 18) | Shared Factor 6 | 6 | No | Both divide evenly by 2, 3, and 6 | |
| (13, 21) | Fibonacci Numbers | 1 | Yes | Neighboring Fibonacci terms are always coprime | |
| (21, 34) | Fibonacci Numbers | 1 | Yes | Neighboring Fibonacci terms are always coprime | |
| (24, 35) | Composite Pair | 1 | Yes | (2³ × 3) and (5 × 7) share no factors | |
| (36, 48) | Shared Factor 12 | 12 | No | Both divide evenly by 12 | |
| (42, 55) | Composite Pair | 1 | Yes | (2 × 3 × 7) and (5 × 11) | |
| (64, 81) | Prime Powers | 1 | Yes | Made only of 2s and 3s (2⁶ and 3⁴) | |
| (84, 126) | Shared Factor 42 | 42 | No | Both divide evenly by 42 | |
| (105, 88) | Odd & Even Pair | 1 | Yes | (3 × 5 × 7) and 2³ × 11 | |
| (143, 169) | Shared Factor 13 | 13 | No | (11 × 13) and 13² | |
| (231, 350) | Shared Factor 7 | 7 | No | Both divide evenly by 7 | |
| (561, 1,105) | Shared Factor 17 | 17 | No | Both divide evenly by 17 | |
| (65,537, 1,000) | Prime & Round Number | 1 | Yes | 65537 is prime and doesn't end in 0 or 5 | |
| (997, 999) | Prime & Composite | 1 | Yes | 997 is prime and does not divide 999 | |
| (1,024, 729) | Powers 2¹⁰ & 3⁶ | 1 | Yes | All 2s vs all 3s | |
| (2,310, 2,431) | Shared Factor 11 | 11 | No | Both divide evenly by 11 | |
| (3,571, 3,572) | Consecutive Numbers | 1 | Yes | Back-to-back numbers always have gcd = 1 | |
| (65,537, 1,048,576) | Internet Security Pair | 1 | Yes | Prime number and power of 2 |
4. Why Back-to-Back Numbers Are Always Coprime
One of the simplest rules in math is that any two consecutive numbers (n and n + 1) are guaranteed to be coprime.
Test Any Back-to-Back Pair
Guaranteed RuleMove the slider to pick a starting number n, and see that n and n + 1 are always coprime:
5. Where Are Coprime Numbers Used in Real Life?
When you visit an encrypted website, your browser uses numbers that are coprime with the server's secret cycle. Because they share no common factors, math guarantees there is a unique matching key that can unlock the message.
When computers store items in memory grids, they jump ahead by a fixed step size. Making that step size coprime to the table size guarantees the search touches every single slot before repeating, preventing clogged slots.
Mechanical engineers deliberately design gear pairs with coprime teeth counts (like 13 and 21 teeth). This ensures every tooth rubs against every other tooth rather than hitting the same spot on every turn, avoiding uneven wear.
Ancient astronomers and modern digital chips use coprime cycle lengths to break huge numbers down into small, quick remainder calculations that can run side-by-side at high speed.
Interactive Gear Wear Simulator
Mechanical DesignChoose the number of teeth on two gears to see if they wear evenly or hit the same teeth repeatedly:
6. What Are the Odds That Two Random Numbers Are Coprime? (~61%)
If you pull two whole numbers completely at random out of a giant hat, what are the odds that they share no common factors? In 1881, mathematician Ernesto Cesàro proved that as numbers get larger, the probability settles precisely at:
This means roughly 6 out of every 10 randomly selected pairs of numbers will be coprime!
Random Number Pair Experiment
6 / π² ≈ 60.79%Roll random number pairs and watch the percentage get closer and closer to 6 / π² (60.79%):
7. Four Clear Examples
8 is made of 2 × 2 × 2 and 9 is made of 3 × 3. They share no common prime factors. Dividing 9 by 8 gives a remainder of 1. Their GCF is 1.
13 is a prime number and does not divide 21 (which is 3 × 7). Because they share no common factors, their GCF is 1.
84 = 2 × 2 × 3 × 7 and 126 = 2 × 3 × 3 × 7. They both divide evenly by 2, 3, and 7 (their product is 42). Because their GCF is 42 (not 1), they are not coprime.
65537 is a prime number. 1000 is only divisible by 2 and 5. Since 65537 is not even and does not end in 0 or 5, the two numbers share no common factors.
8. How Computers Test If Numbers Are Coprime
Different computer methods for checking if two numbers share any common factors:
| Method | Speed | Memory | How It Works | When to Use |
|---|---|---|---|---|
| Euclidean Division | Very Fast | Tiny | Divides larger by smaller and repeats with remainders | Standard everyday numbers |
| Extended Euclidean | Very Fast | Tiny | Divides with remainders while keeping track of multipliers | Finding secret keys in cryptography |
| Binary GCD (Stein's) | Blazing Fast | Tiny | Uses fast binary bit-shifts instead of division | Computer hardware chips |
| Prime Factor Comparison | Slower | Small List | Breaks down both numbers into primes and compares them | Classroom learning and visuals |
Related Factor Calculators
Frequently Asked Questions
What does it mean for two numbers to be coprime?
Two numbers are coprime (also called relatively prime) if their greatest common factor is 1. In plain English, they do not share any common factors or divisors other than the number 1.
Do numbers have to be prime to be coprime?
No. Two composite numbers can easily be coprime as long as they don't share any prime building blocks. For example, 8 (made of 2 × 2 × 2) and 9 (made of 3 × 3) are both composite numbers, but because they share no factors other than 1, they are coprime.
Is 1 coprime with every number?
Yes. The number 1 is coprime with every single positive whole number because the greatest common factor between 1 and any number is always 1.
Why are two back-to-back numbers always coprime?
Any two consecutive numbers (like 14 and 15, or 99 and 100) are guaranteed to be coprime. The difference between them is just 1. Any common factor would also have to divide their difference (1), and the only whole number that divides 1 is 1 itself.
What is Bézout's identity in simple terms?
Bézout's rule shows that you can always multiply your two numbers by whole numbers (positive or negative) and add them together to get their greatest common factor. When two numbers are coprime, you can always make them add up to exactly 1: (a × x) + (b × y) = 1. This math trick is used to create secret decryption keys in cryptography.
Why do secret encryption codes (like RSA) need coprime numbers?
Modern internet security relies on pairs of numbers that share no common factors. When an encryption key number shares no factors with the code system's private clock cycle, math guarantees there is an exact matching partner number that can undo the lock and decrypt the message.
What are the chances that two random numbers are coprime?
If you pick two positive whole numbers completely at random, there is roughly a 60.8% chance (precisely 6 divided by π²) that they share no common factors. This famous result was discovered by mathematician Ernesto Cesàro in 1881.
Why do engineers design machine gears with coprime teeth counts?
If two meshing gears have 13 and 21 teeth (coprime numbers), every tooth on one gear touches every tooth on the other gear before the cycle repeats. This spreads out friction evenly and prevents premature wear and broken teeth.