Coprime Calculator — Check Relatively Prime Numbers
Check if two numbers are coprime (relatively prime) with step-by-step explanation. Find their GCD, see the prime factorizations, and learn about the properties of coprime numbers. For related number theory tools, see our GCD calculator.
Table of Contents
- 1What Are Coprime Numbers?
- 2GCD and the Coprime Test
- 3How to Check for Coprime Numbers
- 4Step-by-Step Examples
- 5More Coprime Examples
- 6Pairwise Coprime Sets
- 7Coprime Numbers and Euler's Totient
- 8Properties of Coprime Numbers
- 9Common Mistakes to Avoid
- 10Real-World Applications
- 11Practice Problems with Solutions
- 12Tips for Mastering Coprime Numbers
- 13Final Thoughts
- 14FAQ: Common Questions
Check If Two Numbers Are Coprime
Enter two positive integers to check if they are coprime. Click Check for step-by-step working.
Coprime Numbers – Complete Explanation
Two numbers are coprime (also called relatively prime or mutually prime) if they share no common factors other than 1. In other words, their greatest common divisor (GCD) is 1. This concept is fundamental to number theory, modular arithmetic, and forms the mathematical foundation of RSA cryptography.
Coprime Definition
Two integers a and b are coprime if and only if GCD(a, b) = 1. Equivalently: They share no common prime factors.
Example: 14 and 25 are coprime (14 = 2 × 7, 25 = 5² — no common primes).
1. What Are Coprime Numbers?
Coprime numbers are "strangers" in the world of divisibility — they have no shared prime building blocks.
Key facts:
- GCD = 1: The defining property.
- No shared prime factors: Their prime factorizations have no primes in common.
- Not the same as prime: Coprime numbers can both be composite.
- 1 is coprime to everything.
- Consecutive integers are always coprime.
2. GCD and the Coprime Test
Coprime Test
a and b are coprime ⇔ GCD(a, b) = 1
3. How to Check for Coprime Numbers
Method 1 — Prime Factorization: Compare sets of distinct primes.
Method 2 — GCD (Euclidean Algorithm): Most efficient for large numbers.
4. Step-by-Step Examples
Example 1: 14 and 25 (Coprime)
14 = 2 × 7 25 = 5² No common primes → GCD(14, 25) = 1 Result: COPRIME! ✓
Example 2: 18 and 30 (Not Coprime)
18 = 2 × 3² 30 = 2 × 3 × 5 Common primes: 2, 3 → GCD(18, 30) = 6 Result: NOT coprime. ✗
5. More Coprime Examples
Coprime: 8 & 15, 9 & 28, 21 & 55
Not Coprime: 12 & 18, 15 & 45, 20 & 30
6. Pairwise Coprime Sets
Pairwise Coprime: {3, 5, 7} — every pair has GCD 1.
Not Pairwise: {6, 10, 15} — overall GCD 1 but GCD(6,10)=2.
7. Coprime Numbers and Euler's Totient
φ(n) counts integers ≤ n that are coprime to n.
φ(12) = 4: 1, 5, 7, 11 are coprime to 12.
8. Properties of Coprime Numbers
• Consecutive integers are coprime.
• 1 is coprime to everything.
• Distinct primes are coprime.
• If coprime, LCM = product.
• φ is multiplicative for coprime numbers.
9. Common Mistakes to Avoid
- Confusing coprime with prime: Coprime numbers can both be composite.
- Thinking coprime means neither divides the other: 4 and 6 are not coprime despite neither dividing the other.
- Forgetting 1 is coprime to everything.
- Assuming numbers with larger gaps are coprime: 15 and 21 differ by 6 but GCD=3.
- Confusing pairwise coprime with set GCD = 1.
10. Real-World Applications
- RSA Cryptography: Public key exponent must be coprime to φ(n).
- Fraction Simplification: Coprime numerator/denominator = simplest form.
- Modular Arithmetic: Multiplicative inverse exists iff coprime to modulus.
- Chinese Remainder Theorem: Requires pairwise coprime moduli.
- Hash Functions: Coprime parameters reduce collisions.
11. Practice Problems with Solutions
Problem 1: Are 17 and 30 coprime? → YES ✓
Problem 2: Are 24 and 35 coprime? → YES ✓
Problem 3: Are 33 and 77 coprime? → NO ✗ (GCD=11)
Problem 4: Numbers ≤ 10 coprime to 10 → 1, 3, 7, 9
12. Tips for Mastering Coprime Numbers
- GCD(a,b) = 1 ⇔ coprime.
- Use Euclidean algorithm for large numbers.
- Consecutive integers are always coprime.
- Distinct primes are always coprime.
- Finding one shared factor (≠1) proves not coprime.
13. Final Thoughts
Coprime numbers represent the fundamental idea of numerical independence. This simple concept has profound consequences — from fractions to cryptography. RSA encryption, securing billions of transactions daily, depends on choosing coprime numbers.
Use this calculator to verify your checks, but practice until the concept becomes intuitive.
14. Frequently Asked Questions
Two numbers are coprime (or relatively prime) if their greatest common divisor (GCD) is 1 — they share no common factors other than 1. For example, 14 and 25 are coprime because 14 = 2×7 and 25 = 5², with no overlapping primes.
No. Coprime numbers can both be composite. For example, 14 and 25 are both composite but coprime (GCD = 1). Two distinct primes are always coprime, but coprime numbers don't have to be prime. The key is that they share no common factors.
Calculate their GCD. If GCD = 1, they are coprime. If GCD > 1, they are not. Alternatively, prime factorize both and check for common primes. The Euclidean algorithm provides an efficient way to compute GCD without factorization.
Yes. GCD(1, n) = 1 for any positive integer n. The number 1 has no prime factors, so it shares no primes with any other number. This makes 1 coprime to everything.
Yes. GCD(n, n+1) = 1 for all positive integers n. This is a fundamental property that can be proved using the Euclidean algorithm: (n+1) - n = 1, so any common divisor must divide 1, meaning it must be 1.
In RSA, the public key exponent e must be coprime to φ(n) = (p-1)(q-1) to ensure that a multiplicative inverse (the private key d) exists. This inverse is computed using the extended Euclidean algorithm. The security and correctness of RSA depend on this coprimality condition.
Euler's totient function φ(n) counts the number of positive integers ≤ n that are coprime to n. For example, φ(12) = 4 because 1, 5, 7, and 11 are the only numbers ≤ 12 that are coprime to 12.
Explore Math Topics
Continue your learning journey with our other math guides
Related Calculators
Explore these other math tools that complement coprime checking:
- 🔹 GCD Calculator — Find the greatest common divisor.
- 🔹 LCM Calculator — Find the least common multiple.
- 🔹 Prime Factorization Calculator — Break numbers into primes.
- 🔹 Euler's Totient Calculator — Calculate φ(n).
- 🔹 Prime Number Checker — Check if a number is prime.
- 🔹 Divisibility Checker — Test if a number divides evenly.
Conclusion
Coprime numbers represent the fundamental idea of numerical independence. Use this calculator to verify your checks, but practice until the concept becomes intuitive and automatic.
Readers who wish to continue practicing and reinforce what they've learned can explore the companion learning resource for guided exercises.