What Is a Co-Prime Number? Definition, Examples and Properties

Co-prime numbers (also called relatively prime numbers) are two numbers whose only common factor is 1, so their HCF (GCD) is 1. For example, 8 and 15 are co-prime: 8 = 2 × 2 × 2 and 15 = 3 × 5 share no prime factor. Neither number needs to be prime itself.

What is a co-prime number?

“Co-prime” describes a pair (or set) of numbers, not a single number. You cannot say “8 is co-prime” on its own; you say “8 and 15 are co-prime”. The test is always the same: find the highest common factor. If HCF(a, b) = 1, then a and b are co-prime.

How to check if two numbers are co-prime

Method 1: prime factorisation

Break both numbers into primes and look for a shared prime.

• 21 = 3 × 7 and 40 = 2 × 2 × 2 × 5. No prime in common, so 21 and 40 are co-prime.
• 18 = 2 × 3 × 3 and 45 = 3 × 3 × 5. They share 3 (in fact 3 × 3 = 9), so 18 and 45 are not co-prime; HCF = 9.

Method 2: Euclid’s algorithm (best for large numbers)

Divide the larger number by the smaller, then keep dividing the previous divisor by the remainder until the remainder is 0. The last non-zero remainder is the HCF.

Are 391 and 299 co-prime?

• 391 = 1 × 299 + 92
• 299 = 3 × 92 + 23
• 92 = 4 × 23 + 0

HCF = 23, so 391 and 299 are not co-prime (391 = 17 × 23, 299 = 13 × 23). Factor-spotting by eye would probably have missed that.

Are 385 and 234 co-prime?

• 385 = 1 × 234 + 151
• 234 = 1 × 151 + 83
• 151 = 1 × 83 + 68
• 83 = 1 × 68 + 15
• 68 = 4 × 15 + 8
• 15 = 1 × 8 + 7
• 8 = 1 × 7 + 1

The last non-zero remainder is 1, so 385 and 234 are co-prime.

Examples of co-prime and non-co-prime pairs

Properties of co-prime numbers

1. Any two different primes are co-prime. A prime’s only factors are 1 and itself, so two different primes cannot share anything but 1.
2. Two consecutive integers are always co-prime. If d divides both n and n + 1, it divides their difference, 1, so d = 1.
3. Two consecutive odd numbers are co-prime. Their difference is 2, so a common factor would have to be 1 or 2, and neither is even.
4. 1 is co-prime with every whole number, including 1 itself.
5. Two even numbers are never co-prime, because 2 divides both.
6. HCF × LCM = product. For any pair, HCF × LCM = a × b. For co-prime numbers the HCF is 1, so LCM = a × b. Example: LCM(8, 15) = 120.
7. Co-prime does not carry across pairs. 4 and 9 are co-prime, 9 and 10 are co-prime, but 4 and 10 are not (both even).

Co-prime numbers vs prime numbers

For more on primes themselves, see why 3 is the smallest odd prime and the prime number program in C.

Where co-prime numbers are used

• Fractions in lowest terms: a fraction a/b is fully simplified exactly when a and b are co-prime. 8/15 cannot be reduced; 12/18 can (to 2/3).
• RSA encryption: the public exponent e must be co-prime with φ(n) = (p − 1)(q − 1), otherwise the private key cannot be computed. The common choice e = 65,537 is itself prime.
• Gear design: engineers often pick tooth counts that are co-prime (for example 17 and 42) so the same pair of teeth meets as rarely as possible, spreading wear evenly. A 17 : 42 pair repeats only after 17 × 42 = 714 tooth engagements.
• Modular arithmetic: a number has a multiplicative inverse mod n only if it is co-prime with n. This is covered in number theory for CS/IT.

FAQs

What is a co-prime number with an example?

Two numbers are co-prime when their HCF is 1. For example, 8 and 15 are co-prime, because 8 = 2³ and 15 = 3 × 5 share no prime factor.

Are 2 and 4 co-prime?

No. Both are divisible by 2, so HCF(2, 4) = 2, not 1.

Do co-prime numbers have to be prime?

No. 9 and 16 are both composite, but they are co-prime because HCF(9, 16) = 1.

Is 1 co-prime with every number?

Yes. The only factor of 1 is 1, so it cannot share any other factor with another number.

What is the LCM of two co-prime numbers?

Their product. Since HCF × LCM = a × b and the HCF is 1, LCM = a × b. For 7 and 9, the LCM is 63.

Related Topics on EngineeringHulk

• 👉 Smallest Odd Prime Number
• 👉 Composite Numbers