Co-prime Numbers: Formula, Properties, Examples and Tricks
Co-prime numbers are two positive integers whose greatest common divisor is 1. They have no common factor other than 1. This page explains the co-prime numbers formula, tests for checking pairs, important properties, counting methods, shortcuts and solved co-prime numbers problems for quantitative aptitude.
What Are Co-prime Numbers?
For example, 8 and 15 are co-prime because the factors of 8 are 1, 2, 4, 8 and the factors of 15 are 1, 3, 5, 15. Their only common factor is 1. The numbers need not both be prime: 8 and 15 are composite, but they are co-prime. Also, 1 is co-prime with every positive integer because gcd(1,n)=1.
Co-prime Numbers Video Lessons
Watch short topic-wise lessons for quick revision.
Types of Numbers Classification
Understand the classification of numbers, including natural, whole, integer, rational, irrational, real and complex numbers, and see how these categories are related in the classification tree.
Co-prime Numbers Formula & Tricks
Important Formulas
The pair a and b is co-prime exactly when its greatest common divisor is 1.
For co-prime numbers, the product itself is their least common multiple.
This relation applies to every pair of positive integers, not only co-prime pairs.
Here p runs over the distinct prime factors of n. φ(n) counts positive integers from 1 to n that are co-prime to n.
Quick Tricks
Any two consecutive integers are co-prime because every common divisor of n and n+1 also divides their difference, which is 1.
If one number is a prime p, the pair is co-prime whenever the other number is not divisible by p.
Repeatedly replace the larger number by the remainder after division. If the final non-zero remainder is 1, the numbers are co-prime.
Co-prime Numbers Concepts
Checking a Pair Using Prime Factors
Write each number as a product of primes and compare the factors. A common prime factor greater than 1 means the pair is not co-prime. For example, 18=2×3² and 25=5², so they have no common prime factor and are co-prime.
Euclidean Algorithm for Large Numbers
If a=bq+r, then gcd(a,b)=gcd(b,r). Continue until the remainder becomes zero. The last non-zero remainder is the GCD; it is 1 for a co-prime pair.
Important Properties of Co-prime Numbers
For every integer n, gcd(n,n+1)=1. If gcd(a,b)=1, then lcm(a,b)=ab. A pair can contain composite numbers and still be co-prime. If a and b are co-prime, then gcd(a+b,a−b) can only be 1 or 2.
Co-prime Pairs Involving Prime Numbers
The only positive factors of p are 1 and p. Therefore, a common factor greater than 1 can exist only when the other number is a multiple of p.
Counting Numbers Co-prime to n
If the distinct prime factors of n are p1,p2,..., then φ(n)=n(1−1/p1)(1−1/p2).... For n=12, the distinct prime factors are 2 and 3, so φ(12)=12×(1−1/2)×(1−1/3)=4.
Co-prime Numbers Data Table
Use the structured data below while following the explanation and examples.
Examples of Co-prime and Non-co-prime Pairs
The GCD determines whether each pair is co-prime.
| Pair | GCD | Result |
|---|---|---|
| 8 and 15 | 1 | Co-prime |
| 14 and 25 | 1 | Co-prime |
| 18 and 30 | 6 | Not co-prime |
| 21 and 35 | 7 | Not co-prime |
| 47 and 48 | 1 | Co-prime |
Note: A pair is co-prime only when its GCD is exactly 1.
Practice Co-prime Numbers Questions
Practise published questions related to this topic.
Co-prime Numbers Quick Quiz
Attempt 5 questions and check your score instantly.
Keep practising
Practice more Co-prime Numbers questions in the PrepShots app and continue from your current topic.
Practice More Questions - Start ₹1 Trial →Quick Revision Notes
Co-prime Numbers: Revision Points
Recall the definition, tests, properties and counting formula for co-prime numbers.
- Co-prime numbers have GCD equal to 1.
- Their only common positive factor is 1.
- Consecutive integers are always co-prime.
- For a co-prime pair a and b, lcm(a,b)=a×b.
- Use prime factorisation or the Euclidean algorithm to find the GCD.
- A prime p is co-prime to n if and only if p does not divide n.
- φ(n)=n∏(1−1/p), where p represents the distinct prime factors of n.
Co-prime Numbers FAQs
Are 8 and 15 co-prime numbers even though both are not prime?
Yes. Their factors have only 1 in common, so gcd(8,15)=1. Co-prime numbers do not need to be prime individually.
Are every pair of odd numbers co-prime?
No. For example, 9 and 15 are both odd, but gcd(9,15)=3. Being odd does not guarantee that a pair is co-prime.
Are every even and odd pair co-prime?
No. For example, 6 and 9 have different parity but gcd(6,9)=3. The pair 8 and 15 is co-prime because its GCD is 1.
What is the co-prime numbers formula for the LCM?
If gcd(a,b)=1, then lcm(a,b)=a×b. For 7 and 12, the LCM is 7×12=84.
How can the Euclidean algorithm check whether 84 and 55 are co-prime?
The remainders are 29, 26, 3, 2 and 1: 84=55+29, 55=29+26, 29=26+3, 26=3×8+2, 3=2+1. The final non-zero remainder is 1, so they are co-prime.
How many numbers from 1 to 18 are co-prime to 18?
φ(18)=18(1−1/2)(1−1/3)=6. The six numbers are 1, 5, 7, 11, 13 and 17.