What Are Co-Prime Numbers

Co-prime numbers, also called relatively prime numbers, are two integers whose only common positive factor is 1. In math notation, two numbers a and b are co-prime when gcd(a, b) = 1.

This definition is small, but it prevents a common mistake: co-prime does not mean both numbers are prime. The numbers can be prime, composite, or one of them can be 1. What matters is whether they share a factor greater than 1.

The Meaning of Co-Prime in Simple Terms

Two numbers are co-prime when they have no shared divisor except 1. Another way to say the same thing is this: their greatest common divisor is 1.

For example, compare 14 and 25. The number 14 is divisible by 1, 2, 7, and 14. The number 25 is divisible by 1, 5, and 25. They share only 1, so they are co-prime.

Now compare 21 and 35. Both are divisible by 7. Since they share a factor greater than 1, they are not co-prime.

Why the GCD Test Works

The greatest common divisor, often written as GCD, is the largest number that divides two integers without a remainder. If the GCD is 1, there is no larger shared divisor. That is exactly what co-prime means.

This is why the condition gcd(a, b) = 1 is the cleanest mathematical test. It avoids guessing, and it works even when the numbers are too large to list all factors by hand.

Example with GCD

Take 18 and 35. The factors of 18 are 1, 2, 3, 6, 9, and 18. The factors of 35 are 1, 5, 7, and 35. The only shared factor is 1, so gcd(18, 35) = 1. That makes 18 and 35 co-prime.

Take 18 and 30. They share 2, 3, and 6. Their GCD is 6, not 1, so they are not co-prime.

Co-Prime Numbers Are Not Always Prime Numbers

This is the point many short calculator-style pages skip. A number can be composite and still be co-prime to another composite number.

Example: 9 and 28 are co-prime. The number 9 is composite because 9 = 3 × 3. The number 28 is composite because 28 = 2 × 2 × 7. They do not share any prime factor, so their GCD is 1.

That is the deeper pattern: co-primality is about shared factors, not about whether each number is prime on its own.

Prime Factors Make Co-Prime Numbers Easier to See

Every integer greater than 1 can be broken into prime factors. If two numbers have no prime factor in common, they are co-prime.

Look at 40 and 63:

• 40 = 2 × 2 × 2 × 5
• 63 = 3 × 3 × 7

There is no shared prime factor. So 40 and 63 are co-prime.

Now look at 40 and 70:

• 40 = 2 × 2 × 2 × 5
• 70 = 2 × 5 × 7

They share 2 and 5. So they are not co-prime.

If you want to check whether a single number is prime before comparing it with another number, you can use the Prime Number Checker. It helps separate prime numbers from composite numbers, which makes factor-based reasoning easier.

Common Examples of Co-Prime and Non-Co-Prime Numbers

Useful Patterns for Recognizing Co-Prime Numbers

Some patterns help you recognize co-prime numbers without listing every factor. These are not magic shortcuts. They work because they come from the same GCD idea.

Consecutive Integers Are Always Co-Prime

Any two consecutive integers, such as 24 and 25 or 100 and 101, are co-prime. A number greater than 1 cannot divide two numbers that are only 1 apart.

If a shared divisor d divided both n and n + 1, then d would also have to divide their difference, which is 1. The only positive divisor of 1 is 1. So the GCD must be 1.

Two Different Prime Numbers Are Always Co-Prime

For example, 17 and 23 are co-prime. A prime number has only two positive factors: 1 and itself. Two different primes cannot share a factor greater than 1.

A Prime Number and a Non-Multiple Can Be Co-Prime

A prime number is co-prime with any number that is not divisible by it. For example, 7 and 20 are co-prime because 20 is not divisible by 7.

But 7 and 21 are not co-prime because 21 is divisible by 7.

The Number 1 Is Co-Prime With Every Integer

The number 1 has only one positive factor: itself. Since it has no factor greater than 1, 1 is co-prime with every integer.

This may feel odd at first because 1 is not a prime number. But co-prime status depends on shared factors, not on whether the number itself is prime.

Pairwise Co-Prime vs Co-Prime as a Group

When more than two numbers appear, the wording needs care. A set of numbers can have a GCD of 1 as a group, but the numbers may not be pairwise co-prime.

Pairwise Co-Prime

A group is pairwise co-prime when every possible pair inside the group is co-prime.

For example, 5, 8, and 21 are pairwise co-prime:

• 5 and 8 share only 1.
• 5 and 21 share only 1.
• 8 and 21 share only 1.

Co-Prime as a Whole

Now look at 6, 10, and 15. Their group GCD is 1, but they are not pairwise co-prime:

• 6 and 10 share 2.
• 6 and 15 share 3.
• 10 and 15 share 5.

So the phrase pairwise co-prime is stronger. It says every pair passes the GCD test, not just the full group.

How Co-Prime Numbers Connect to Fractions

A fraction is in lowest terms when its numerator and denominator are co-prime.

For example, 8/15 is already reduced because 8 and 15 are co-prime. There is no common factor greater than 1 that can be divided out.

But 12/18 is not in lowest terms because 12 and 18 share 6. Dividing both by 6 gives 2/3. The numbers 2 and 3 are co-prime, so the reduced fraction stops there.

This is one reason co-prime numbers show up early in number theory. They explain why some fractions can be simplified and why others cannot.

How Co-Prime Numbers Connect to Modular Arithmetic

Co-prime numbers also matter in modular arithmetic, where numbers wrap around after reaching a modulus. A number has a modular inverse modulo n only when it is co-prime with n.

For example, 5 has an inverse modulo 12 because gcd(5, 12) = 1. In fact, 5 × 5 = 25, and 25 leaves a remainder of 1 when divided by 12. So 5 is its own inverse modulo 12.

But 6 has no inverse modulo 12 because gcd(6, 12) = 6. The shared factor blocks the inverse.

This idea later connects to Euler’s totient function, reduced residue systems, and public-key encryption. In standard RSA setup, for example, an exponent is chosen so it is co-prime with a value based on the prime factors of the modulus.

Euclid’s Algorithm and the Oldest Practical Test

One of the cleanest ways to test co-primality is Euclid’s algorithm. It finds the GCD by using remainders instead of listing all factors.

For small numbers, factor lists are fine. For larger numbers, the Euclidean method is faster and easier to trust. It also gives a better view of why GCD is the natural test for co-prime numbers.

Example: 35 and 64

These two numbers are co-prime because the repeated remainder process ends at 1:

• 64 = 1 × 35 + 29
• 35 = 1 × 29 + 6
• 29 = 4 × 6 + 5
• 6 = 1 × 5 + 1
• 5 = 5 × 1 + 0

The last non-zero remainder is 1, so gcd(35, 64) = 1. That means 35 and 64 are co-prime.

Special Cases That Often Cause Confusion

Is 1 a Prime Number?

No. The number 1 is not prime because a prime number must have exactly two positive factors. The number 1 has only one. Still, 1 is co-prime with every integer because it shares no factor greater than 1 with any number.

Can Negative Numbers Be Co-Prime?

Yes, if the idea is handled through absolute values. For example, -8 and 15 are co-prime because 8 and 15 have GCD 1. The sign does not create a new shared factor.

Is 0 Co-Prime With Any Number?

Zero needs care. Since gcd(0, n) = |n|, zero is co-prime only with 1 and -1. For example, 0 and 7 are not co-prime because their GCD is 7.

Are Twin Primes the Same as Co-Prime Numbers?

No. Twin primes are prime numbers that differ by 2, such as 11 and 13. They are co-prime, but the two ideas are not the same. Co-prime numbers only need GCD 1; they do not need to be prime and they do not need to be 2 apart.

Why Co-Prime Numbers Matter

Co-prime numbers appear in many parts of number theory because they show when two numbers are independent in a divisibility sense. They do not share a prime factor, so one number does not carry a hidden divisor from the other.

This matters in:

• Fractions: a fraction is reduced when the numerator and denominator are co-prime.
• Prime factorization: shared prime factors decide whether the GCD is greater than 1.
• Modular arithmetic: inverses require co-prime numbers.
• Euler’s totient function: φ(n) counts positive integers up to n that are co-prime with n.
• Cryptography: many number-theory systems rely on carefully chosen co-prime values.

That is why co-prime numbers deserve more than a yes-or-no answer. The concept links factorization, GCD, reduced fractions, modular inverses, and prime-based systems.

Simple Way to Think About Co-Prime Numbers

When you compare two numbers, ask one clean question:

Do these numbers share any factor greater than 1?

If the answer is no, they are co-prime. If the answer is yes, they are not.

For deeper checking, use the GCD. For factor-based learning, break the numbers into prime factors. Both paths lead to the same result, but prime factorization shows the reason more clearly.

FAQ About Co-Prime Numbers