Skip to main content

Coprime Calculator

Mathematics - Coprime Numbers

Coprime Calculator

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 and applications of coprime numbers in number theory and cryptography.

Table of Contents

  1. 1What Are Coprime Numbers?
  2. 2GCD and the Coprime Test
  3. 3How to Check for Coprime Numbers
  4. 4Step-by-Step Examples
  5. 5More Coprime Examples
  6. 6Pairwise Coprime Sets
  7. 7Coprime Numbers and Euler's Totient
  8. 8Properties of Coprime Numbers
  9. 9Common Mistakes to Avoid
  10. 10Real-World Applications
  11. 11Practice Problems with Solutions
  12. 12Tips for Mastering Coprime Numbers
  13. 13Final Thoughts

Check If Two Numbers Are Coprime

Enter two positive integers to check if they are coprime (relatively prime). Click Check for step-by-step working using prime factorization and GCD.

Result will appear here.
Note: Two numbers are coprime (or relatively prime) if their greatest common divisor (GCD) is 1 — meaning they share no common prime factors. Equivalent terms include "mutually prime" and "strangers." Coprime numbers play a crucial role in modular arithmetic, Euler's theorem, and RSA cryptography.

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. The only positive integer that divides both is 1.

Key facts:

  • GCD = 1: The defining property of coprime numbers.
  • No shared prime factors: Their prime factorizations have no primes in common.
  • Not the same as prime: Coprime numbers can both be composite (e.g., 14 and 25).
  • 1 is coprime to everything: GCD(1, n) = 1 for any n.
  • Consecutive integers are always coprime: GCD(n, n+1) = 1 for all n.

2. GCD and the Coprime Test

The greatest common divisor (GCD) is the definitive test for coprimality:

Coprime Test

a and b are coprime ⇔ GCD(a, b) = 1

If the GCD is anything other than 1, the numbers are not coprime.

This single test replaces the need to compare all factors. The Euclidean algorithm provides an efficient way to compute the GCD even for very large numbers without factoring them.

3. How to Check for Coprime Numbers

There are two main methods:

Method 1 — Prime Factorization Comparison:

1. Prime factorize both numbers.

2. Compare the sets of distinct prime factors.

3. If they share any prime → not coprime. If they share none → coprime.

• Best for: Understanding why numbers are or aren't coprime.

Method 2 — GCD Calculation (Euclidean Algorithm):

1. Calculate GCD(a, b) using the Euclidean algorithm.

2. If GCD = 1 → coprime. If GCD > 1 → not coprime.

• Best for: Efficiency, especially with large numbers.

4. Step-by-Step Examples

Example 1: 14 and 25 (Coprime)

Check if 14 and 25 are coprime.

Method 1 — Prime Factorization:
Step 1: 14 = 2 × 7
        25 = 5 × 5 = 5²

Step 2: Common primes?
        Primes in 14: {2, 7}
        Primes in 25: {5}
        No common primes!

Method 2 — GCD:
        GCD(14, 25) = 1

Result: 14 and 25 ARE COPRIME! ✓

Example 2: 18 and 30 (Not Coprime)

Check if 18 and 30 are coprime.

Method 1 — Prime Factorization:
Step 1: 18 = 2 × 3²
        30 = 2 × 3 × 5

Step 2: Common primes: {2, 3}
        They share primes 2 and 3 → NOT coprime!

Method 2 — GCD:
        GCD(18, 30) = 6 ≠ 1

Result: 18 and 30 are NOT coprime. ✗
        They share common factors: 2, 3, and 6.

5. More Coprime Examples

Coprime Pairs (GCD = 1):

• 8 and 15 → 8=2³, 15=3×5 → no common primes → COPRIME ✓

• 9 and 28 → 9=3², 28=2²×7 → no common primes → COPRIME ✓

• 21 and 55 → 21=3×7, 55=5×11 → no common primes → COPRIME ✓

Non-Coprime Pairs (GCD > 1):

• 12 and 18 → GCD = 6 → NOT COPRIME ✗

• 15 and 45 → GCD = 15 → NOT COPRIME ✗

• 20 and 30 → GCD = 10 → NOT COPRIME ✗

6. Pairwise Coprime Sets

A set of numbers is pairwise coprime if every pair in the set is coprime. This is stronger than the set simply having GCD 1 overall.

Pairwise Coprime: {3, 5, 7}

GCD(3,5)=1, GCD(3,7)=1, GCD(5,7)=1 → Pairwise coprime ✓

Not Pairwise Coprime: {6, 10, 15}

GCD(6,10,15)=1 but GCD(6,10)=2 → Not pairwise coprime ✗

The set has overall GCD 1, but pairs within it share factors.

7. Coprime Numbers and Euler's Totient

Euler's totient function φ(n) counts the number of positive integers ≤ n that are coprime to n. This connects the concept of coprimality directly to one of the most important functions in number theory.

φ(12) = 4: Numbers ≤ 12 that are coprime to 12:

1, 5, 7, 11 → 4 numbers

These are exactly the numbers k (1 ≤ k ≤ 12) where GCD(k, 12) = 1.

Euler's Theorem: If a and n are coprime, then aφ(n) ≡ 1 (mod n). This theorem is the foundation of RSA encryption and relies entirely on the concept of coprimality.

8. Properties of Coprime Numbers

1. Consecutive integers are always coprime: GCD(n, n+1) = 1 for all n.

2. 1 is coprime to every integer: GCD(1, n) = 1 for all n.

3. Two distinct primes are always coprime: If p ≠ q and both are prime, GCD(p, q) = 1.

4. If a and b are coprime, then LCM(a,b) = a × b: No common factors means the product is the LCM.

5. Euler's totient is multiplicative for coprime numbers: If GCD(a, b) = 1, then φ(ab) = φ(a) × φ(b).

6. If d divides both a and b, then a and b are coprime only if d = 1: The only common divisor of coprime numbers is 1.

9. Common Mistakes to Avoid

  • Confusing coprime with prime: Coprime numbers can both be composite. 14 and 25 are coprime but neither is prime. Two primes are always coprime (unless they're the same prime).
  • Thinking coprime means neither divides the other: 4 and 6 don't divide each other, but GCD(4,6)=2, so they're not coprime. Coprime is about shared factors, not divisibility.
  • Forgetting that 1 is coprime to everything: GCD(1, n) = 1 is always true, making 1 a special case.
  • Assuming consecutive odds are coprime: 15 and 21 are both odd and differ by 6, but GCD(15,21)=3. Consecutive integers (n, n+1) are always coprime, but numbers with larger gaps may not be.
  • Confusing pairwise coprime with set GCD = 1: {6, 10, 15} has overall GCD 1, but the pairs are not coprime. Pairwise coprime is a stronger condition.

10. Real-World Applications

  • RSA Cryptography: The public key exponent e must be coprime to φ(n) for the encryption to work. This is the most commercially significant application of coprimality.
  • Fraction Simplification: If the numerator and denominator are coprime, the fraction is already in simplest form.
  • Modular Arithmetic: A number a has a multiplicative inverse modulo n if and only if a and n are coprime.
  • Chinese Remainder Theorem: The moduli must be pairwise coprime for the theorem to guarantee a unique solution.
  • Geometry: The slope of a line in lowest terms involves coprime numerator and denominator.
  • Hash Functions: Choosing coprime parameters helps avoid collisions in hash table implementations.

11. Practice Problems with Solutions

Problem 1: Are 17 and 30 coprime?

Solution: 17=17, 30=2×3×5 → no common primes → GCD=1 → YES, COPRIME ✓

Problem 2: Are 24 and 35 coprime?

Solution: 24=2³×3, 35=5×7 → no common primes → GCD=1 → YES, COPRIME ✓

Problem 3: Are 33 and 77 coprime?

Solution: 33=3×11, 77=7×11 → common prime 11 → GCD=11 → NO ✗

Problem 4: Find all numbers ≤ 10 that are coprime to 10.

Solution: 10=2×5. Coprime numbers: 1, 3, 7, 9 → 4 numbers = φ(10)

12. Tips for Mastering Coprime Numbers

  • Remember the golden rule: GCD(a, b) = 1 ⇔ a and b are coprime.
  • Use prime factorization to understand WHY numbers are or aren't coprime.
  • Use the Euclidean algorithm for efficiency with large numbers.
  • Consecutive integers are always coprime — this is a useful shortcut.
  • Two different primes are always coprime — they have no shared factors by definition.
  • If you can find even one shared factor (other than 1), the numbers are not coprime.

13. Final Thoughts

Coprime numbers represent the fundamental idea of numerical independence — they share no common building blocks. This simple concept has profound consequences throughout mathematics, from the structure of fractions to the security of modern cryptography. The fact that RSA encryption, which secures billions of online transactions daily, depends on choosing numbers that are coprime to one another demonstrates the practical power of this elegant concept.

Master the coprime test — GCD = 1 — and understand how prime factorization reveals the underlying reasons. Use this calculator to verify your checks, but practice identifying coprime pairs until the concept becomes intuitive and automatic.

Labels: