Co-Prime Checker: Finally Understand Relatively Prime Numbers
Let me tell you about the first time I heard the term "co-prime." I was in math class, and my teacher said, "15 and 28 are co-prime." I thought, "Neither of them is prime—how can they be co-prime?"
Then I learned: co-prime (or relatively prime) means two numbers share no common factors other than 1. They don't need to be prime themselves. And once you understand this, concepts like modular arithmetic, RSA encryption, and fraction simplification become much clearer.
In this guide, I'll walk you through everything you need to know about co-prime numbers—from the Euclidean algorithm to real-world applications in cryptography.
Ready to master co-prime numbers? Try our Co-Prime Checker and watch the Euclidean algorithm unfold step by step.
What Are Co-Prime Numbers?
Two numbers are co-prime (or relatively prime) if their Greatest Common Divisor (GCD) is 1. This means they share no common prime factors.
Simple Examples
| Pair | GCD | Co-Prime? | Why |
|---|---|---|---|
| (8, 15) | 1 | ✓ | 8 = 2³, 15 = 3 × 5 — no common factors |
| (9, 28) | 1 | ✓ | 9 = 3², 28 = 2² × 7 — no common factors |
| (12, 18) | 6 | ✗ | Share factors 2 and 3 |
| (14, 21) | 7 | ✗ | Share factor 7 |
| (1, any n) | 1 | ✓ | 1 is co-prime with every number |
Key Insight
Co-prime doesn't mean prime!
- 8 is composite (2 × 2 × 2)
- 15 is composite (3 × 5)
- Yet 8 and 15 are co-prime because they share no common factors
Why Co-Prime Numbers Matter
| Field | Application |
|---|---|
| Cryptography | RSA encryption uses co-prime numbers for key generation |
| Modular arithmetic | Modular inverses exist only when numbers are co-prime |
| Fractions | A fraction is in simplest form when numerator and denominator are co-prime |
| Chinese Remainder Theorem | Requires co-prime moduli |
| Music theory | Consonant intervals often use co-prime frequency ratios |
| Clock arithmetic | Co-prime step sizes cycle through all residues |
The Euclidean Algorithm: A 2,300-Year-Old Method
The Euclidean algorithm, discovered by Euclid around 300 BCE, is an efficient way to find the GCD of two numbers.
How It Works
For two numbers a and b (a ≥ b):
- Divide a by b, get remainder r
- Replace a with b, b with r
- Repeat until remainder = 0
- The last non-zero remainder is the GCD
Why It Works
The key insight: GCD(a, b) = GCD(b, a mod b)
If a number divides both a and b, it also divides their remainder. So we can keep reducing the problem until one number becomes 0.
Step-by-Step Examples
Example 1: Check if 8 and 15 are Co-Prime
Step 1: Compare numbers (15 > 8)
- 15 ÷ 8 = 1 remainder 7
- 15 = 1 × 8 + 7
Step 2: Now check 8 and 7
- 8 ÷ 7 = 1 remainder 1
- 8 = 1 × 7 + 1
Step 3: Now check 7 and 1
- 7 ÷ 1 = 7 remainder 0
- 7 = 7 × 1 + 0
Step 4: GCD = 1
Result: 8 and 15 are CO-PRIME ✓
Example 2: Check if 12 and 18 are Co-Prime
Step 1: 18 ÷ 12 = 1 remainder 6
- 18 = 1 × 12 + 6
Step 2: 12 ÷ 6 = 2 remainder 0
- 12 = 2 × 6 + 0
Step 3: GCD = 6
Result: 12 and 18 are NOT co-prime ✗
Example 3: Check if 876757 and 768715 are Co-Prime
This is the example loaded in our calculator.
Step 1: 876757 ÷ 768715 = 1 remainder 108042
- 876757 = 1 × 768715 + 108042
Step 2: 768715 ÷ 108042 = 7 remainder 12421
- 768715 = 7 × 108042 + 12421
Step 3: 108042 ÷ 12421 = 8 remainder 9274
- 108042 = 8 × 12421 + 9274
Step 4: 12421 ÷ 9274 = 1 remainder 3147
- 12421 = 1 × 9274 + 3147
Step 5: 9274 ÷ 3147 = 2 remainder 2980
- 9274 = 2 × 3147 + 2980
Step 6: 3147 ÷ 2980 = 1 remainder 167
- 3147 = 1 × 2980 + 167
Step 7: 2980 ÷ 167 = 17 remainder 141
- 2980 = 17 × 167 + 141
Step 8: 167 ÷ 141 = 1 remainder 26
- 167 = 1 × 141 + 26
Step 9: 141 ÷ 26 = 5 remainder 11
- 141 = 5 × 26 + 11
Step 10: 26 ÷ 11 = 2 remainder 4
- 26 = 2 × 11 + 4
Step 11: 11 ÷ 4 = 2 remainder 3
- 11 = 2 × 4 + 3
Step 12: 4 ÷ 3 = 1 remainder 1
- 4 = 1 × 3 + 1
Step 13: 3 ÷ 1 = 3 remainder 0
- 3 = 3 × 1 + 0
GCD = 1 → These numbers are CO-PRIME!
Co-Prime vs. Prime: Key Differences
| Property | Prime Number | Co-Prime Pair |
|---|---|---|
| Definition | Number with exactly 2 divisors | Two numbers with GCD = 1 |
| Example | 7 is prime | (8, 15) are co-prime |
| Individual numbers | Must be prime | Can be composite |
| 1's role | 1 is NOT prime | 1 is co-prime with everything |
Examples to Illustrate
| Pair | Both Prime? | Co-Prime? |
|---|---|---|
| (5, 7) | ✓ | ✓ (different primes) |
| (5, 5) | ✓ | ✗ (same prime, GCD=5) |
| (8, 15) | ✗ (both composite) | ✓ (no common factors) |
| (8, 12) | ✗ | ✗ (share factor 4) |
| (1, 100) | ✗ | ✓ (1 is special) |
Properties of Co-Prime Numbers
Property 1: Consecutive Numbers Are Always Co-Prime
Any two consecutive integers (n, n+1) are co-prime.
Examples:
- (5, 6) → GCD = 1
- (99, 100) → GCD = 1
- (1000, 1001) → GCD = 1
Why? Any common divisor must divide their difference (which is 1).
Property 2: 1 is Co-Prime with Every Number
GCD(1, n) = 1 for all n ≥ 1.
Property 3: Two Different Primes Are Always Co-Prime
If p and q are distinct primes, GCD(p, q) = 1.
Examples: (2, 3), (5, 11), (13, 17)
Property 4: Prime and Non-Multiple Are Co-Prime
If p is prime and p does not divide n, then GCD(p, n) = 1.
Examples: (7, 12), (13, 25)
Property 5: Linear Combination
If GCD(a, b) = 1, there exist integers x and y such that:
ax + by = 1
This is called Bézout's identity.
Example for (8, 15): 8 × 2 + 15 × (-1) = 16 - 15 = 1
Co-Primes in Fractions
A fraction is in simplest form when numerator and denominator are co-prime.
Examples
| Fraction | GCD | Simplified? |
|---|---|---|
| 8/15 | 1 | ✓ (already simplified) |
| 12/18 | 6 | ✗ (simplifies to 2/3) |
| 9/28 | 1 | ✓ |
| 14/21 | 7 | ✗ (simplifies to 2/3) |
How to Simplify Using Co-Prime Check
- Find GCD of numerator and denominator
- If GCD = 1, fraction is already simplified
- If GCD > 1, divide both by GCD
Example: Simplify 12/18
- GCD(12, 18) = 6
- 12 ÷ 6 = 2, 18 ÷ 6 = 3
- Simplified: 2/3
Co-Primes in Cryptography (RSA)
RSA encryption relies heavily on co-prime numbers.
Key Generation Steps
- Choose two large primes p and q
- Compute n = p × q
- Compute φ(n) = (p - 1)(q - 1)
- Choose e such that GCD(e, φ(n)) = 1 (e is co-prime to φ(n))
- Find d such that e × d ≡ 1 (mod φ(n))
The numbers e and φ(n) must be co-prime for the modular inverse to exist.
Why Co-Primes Matter in RSA
- If e and φ(n) share a common factor > 1, the decryption key d doesn't exist
- Co-primality ensures the encryption is reversible
- This is why RSA works!
Modular Inverses
A modular inverse of a modulo m exists if and only if a and m are co-prime.
Definition
a × a⁻¹ ≡ 1 (mod m)
Example
Find inverse of 3 modulo 7:
- 3 × 5 = 15 ≡ 1 (mod 7)
- So 5 is the inverse of 3 modulo 7
Why Co-Prime Matters
If GCD(a, m) ≠ 1, no inverse exists.
Example: Find inverse of 4 modulo 6
- 4 × 1 = 4, 4 × 2 = 8 ≡ 2, 4 × 3 = 12 ≡ 0, 4 × 4 = 16 ≡ 4...
- Never get 1 mod 6 → no inverse exists
How to Use Our Co-Prime Checker
Step 1: Enter Two Numbers
Type any positive integers. Example: 876757 and 768715
Step 2: Click Check Now
The calculator performs the Euclidean algorithm step by step.
Step 3: Read Your Results
You'll see:
- GCD: The greatest common divisor
- Co-Prime status: Yes (if GCD = 1) or No
- Euclidean steps: Each division shown sequentially
- Visual representation: Color-coded result card
What It Handles
| Input | Example | Works? |
|---|---|---|
| Small numbers | 8, 15 | ✓ |
| Large numbers | 876757, 768715 | ✓ |
| Very large | Up to 1 trillion | ✓ |
| Equal numbers | 12, 12 | ✓ (GCD = 12, not co-prime) |
| 1 with anything | 1, 100 | ✓ (co-prime) |
| Prime pairs | 17, 19 | ✓ (co-prime) |
| Consecutive | 100, 101 | ✓ (co-prime) |
| Invalid inputs | negative, zero | ⚠️ Error message |
Common Mistakes
Mistake 1: Thinking Composite Numbers Can't Be Co-Prime
Wrong: "8 and 15 are both composite, so they can't be co-prime" Right: Composite numbers can be co-prime if they share no common factors.
Mistake 2: Confusing Co-Prime with Prime
Wrong: "Co-prime means both numbers are prime" Right: Co-prime means GCD = 1, regardless of whether numbers are prime.
Mistake 3: Forgetting 1 is Co-Prime with Everything
Wrong: "1 isn't co-prime with anything because it's not prime" Right: 1 is co-prime with every positive integer.
Mistake 4: Thinking Same Numbers Can Be Co-Prime
Wrong: "12 and 12 are co-prime because they're the same" Right: GCD(12, 12) = 12, not 1, so not co-prime.
Mistake 5: Stopping Euclidean Algorithm Early
Wrong: Stop when remainder is small but not zero Right: Continue until remainder = 0. The last non-zero remainder is GCD.
Quick Reference: Co-Prime Pairs
| Pair | Co-Prime? | GCD |
|---|---|---|
| (2, 3) | ✓ | 1 |
| (2, 4) | ✗ | 2 |
| (3, 5) | ✓ | 1 |
| (4, 9) | ✓ | 1 |
| (6, 10) | ✗ | 2 |
| (7, 11) | ✓ | 1 |
| (8, 9) | ✓ | 1 |
| (8, 12) | ✗ | 4 |
| (9, 16) | ✓ | 1 |
| (10, 15) | ✗ | 5 |
| (12, 25) | ✓ | 1 |
| (14, 21) | ✗ | 7 |
| (15, 28) | ✓ | 1 |
| (16, 27) | ✓ | 1 |
| (18, 25) | ✓ | 1 |
| (20, 21) | ✓ | 1 |
| (21, 28) | ✗ | 7 |
| (24, 35) | ✓ | 1 |
| (25, 36) | ✓ | 1 |
| (27, 64) | ✓ | 1 |
Fun Facts About Co-Prime Numbers
Consecutive Integers
Any two consecutive integers are always co-prime. Try (100, 101), (1000, 1001), (1,000,000, 1,000,001)!
Prime Pairs
Two different primes are always co-prime. (2, 3), (5, 7), (13, 17), (31, 37)
The Euclidean Algorithm
This algorithm is over 2,300 years old and is still the most efficient way to find GCD!
RSA Encryption
The security of online banking and e-commerce relies on co-prime numbers.
Probability
If you pick two random integers, the probability they are co-prime is about 61% (specifically, 6/π² ≈ 0.6079).
Frequently Asked Questions
What's the difference between co-prime and relatively prime?
Nothing! They mean exactly the same thing.
Is 1 co-prime with 1?
Yes. GCD(1, 1) = 1, so 1 and 1 are co-prime.
Are 0 and 5 co-prime?
By convention, GCD(0, n) = |n|. So GCD(0, 5) = 5, not 1. Most definitions require positive integers.
Can negative numbers be co-prime?
Yes, co-primality ignores signs. (-8, 15) have GCD = 1.
What's the probability two random numbers are co-prime?
6/π² ≈ 0.6079 (about 61%).
Why is the Euclidean algorithm efficient?
Each step reduces the numbers significantly. The number of steps is O(log n).
How does your calculator handle large numbers?
It works with numbers up to 1 trillion (1,000,000,000,000).
What's Bézout's identity?
If GCD(a, b) = 1, there exist integers x and y such that ax + by = 1.
Your Turn: Start Checking
Co-prime numbers used to confuse me. Now I understand they're simply numbers that share no common factors—their GCD is 1.
Here's your practice plan:
- Start with simple pairs: (8, 15), (9, 28), (12, 25)
- Try consecutive numbers: (5, 6), (99, 100), (1000, 1001)
- Test prime pairs: (13, 17), (19, 23), (29, 31)
- Check non-co-prime pairs: (12, 18), (14, 21), (25, 35)
- Try the special case: (1, anything)
- Use large numbers: (876757, 768715) from our example
- Watch the Euclidean steps: See how numbers reduce to GCD
Ready to start? Open up our Co-Prime Checker and try it yourself. Start with 8, 15, then 12, 18, then 876757, 768715.
You'll master co-prime numbers faster than you think.
Have questions? Stuck on a particular pair? Drop a comment below or reach out. I've been where you are, and I'm happy to help.
— The Solvezi Team
Disclaimer: This calculator is for educational purposes. While we aim for accuracy, always double-check critical calculations independently.
