An Initiative by SAARTHI IAS
Maarg Manthan · Topic 1.6

Prime Numbers, Composite Numbers and Co-Prime Numbers

Quantitative Aptitude › Number System · Topic 1.6

A prime number is a natural number greater than 1 with exactly two factors, 1 and itself. A composite number has more than two factors, and two numbers are co-prime when their only common factor is 1.

Share:
Prime Numbers, Composite Numbers and Co-Prime Numbers - Quantitative Aptitude - MaargX UPSC Maarg Manthan

Quick Answer

A prime number is a natural number greater than 1 with exactly two factors, 1 and itself. A composite number has more than two factors, and two numbers are co-prime when their only common factor is 1.

At a Glance

  • Prime Exactly two factors
  • Smallest prime 2, the only even prime
  • Primes below 100 25
  • 1 Neither prime nor composite
  • Co-prime pair HCF equals 1
  • Primality test Divide by primes up to the square root

Where Does It Fit?

This topic follows Number of Factors, Sum of Factors and Product of Factors of a Number, where prime factorization was used. It prepares Factorial Values and Number of Trailing Zeros in a Factorial, Fermat’s Little Theorem and Wilson’s Theorem Applications and the HCF work in Highest Common Factor (HCF) by Division and Prime Factorization Method, which all rely on prime and co-prime ideas.

What Are Prime, Composite and Co-Prime Numbers?

In short: primes cannot be broken into smaller factors, composites can, and co-prime describes a pair that shares no factor except 1.

  • Prime numbers: 2, 3, 5, 7, 11, 13, … Each has exactly two factors.
  • Composite numbers: 4, 6, 8, 9, 10, 12, … Each has more than two factors.
  • The number 1: it has only one factor, so it is neither prime nor composite.
  • Even prime: 2 is the only even prime, because every other even number is divisible by 2.
  • Co-prime numbers: two numbers whose highest common factor is 1. The numbers themselves need not be prime, so 35 and 64 are co-prime.
Pair Common factor Co-prime?
8, 15 1 Yes
35, 64 1 Yes
12, 18 6 No
21, 22 1 Yes, consecutive numbers
7, 13 1 Yes, two primes

Any two consecutive integers are co-prime, and any two different primes are co-prime. The highest common factor itself is developed in Highest Common Factor (HCF) by Division and Prime Factorization Method.

How Do You Test Whether a Number Is Prime?

In short: divide the number by every prime up to its square root. If none divides it, the number is prime.

  • For 391, the square root is about 19.8, so test the primes 2, 3, 5, 7, 11, 13, 17 and 19. Since 17 × 23 = 391, it is composite.
  • For 289, the square root is exactly 17, and 17 × 17 = 289, so it is composite.
  • For 101, test 2, 3, 5 and 7 (the square root is about 10.05). None divides it, so 101 is prime.

The primes below 100 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. There are 25 of them, and 10 lie between 50 and 100. Every prime greater than 3 has the form 6k – 1 or 6k + 1, though not every such number is prime.

What Are Twin Primes and How Do You Count Co-Prime Numbers?

In short: twin primes differ by 2, and the count of numbers up to n that are co-prime to n comes from its prime factors.

  • Twin primes: pairs such as (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) and (41, 43). Below 50 there are 6 such pairs.
  • Co-prime counting: the number of integers from 1 to n that are co-prime to n is n × (1 – 1/p)(1 – 1/q)… over each prime factor p, q of n. This is the Euler totient.
  • For 30 = 2 × 3 × 5, the count is 30 × 1/2 × 2/3 × 4/5 = 8: 1, 7, 11, 13, 17, 19, 23 and 29.

Co-prime counting

  • Numbers up to n co-prime to n = n × (1 – 1/p) × (1 – 1/q) … for each prime factor.
  • For a prime p, it is p – 1.

Solved Examples

Example 1

Question: Is 391 a prime number?

  1. The square root of 391 is a little under 20, so test primes up to 19.
  2. 391 ÷ 17 = 23 exactly.
  3. So 391 = 17 × 23.

Answer: No, 391 is composite.

Example 2

Question: How many prime numbers lie between 50 and 100?

  1. The primes in this range are 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97.
  2. Count them: 10.

Answer: 10.

Example 3

Question: Are 35 and 64 co-prime?

  1. 35 = 5 × 7 and 64 = 26.
  2. They share no prime factor.
  3. So their highest common factor is 1.

Answer: Yes, they are co-prime.

Example 4

Question: How many numbers from 1 to 30 are co-prime to 30?

  1. 30 = 2 × 3 × 5.
  2. Count = 30 × (1/2) × (2/3) × (4/5) = 8.
  3. They are 1, 7, 11, 13, 17, 19, 23, 29.

Answer: 8 numbers.

Example 5

Question: Show that 1,001 is composite.

  1. Try small primes: 1,001 ÷ 7 = 143.
  2. 143 = 11 × 13.
  3. So 1,001 = 7 × 11 × 13.

Answer: 1,001 is composite.

Shortcuts and Tricks

  • Remember the 25 primes below 100; they appear again and again.
  • To test a number up to 400, divide by 2, 3, 5, 7, 11, 13, 17 and 19 only.
  • Use the divisibility rules from Divisibility Rules for 2 to 19 instead of long division.
  • Two numbers differing by 1 are always co-prime.
  • For co-prime counting, only the distinct prime factors of n matter.

Common Mistakes

  • Calling 1 a prime number. It has only one factor.
  • Calling 2 a composite because it is even. It is prime.
  • Assuming co-prime numbers must both be prime. 8 and 15 are co-prime but neither is prime.
  • Stopping the primality test too early or going beyond the square root unnecessarily.
  • Using the 6k ± 1 form as a test; many numbers of that form, such as 25, are composite.

Practice Questions

  1. Is 97 a prime number?
  2. What is the smallest prime number greater than 100?
  3. Are 21 and 22 co-prime?
  4. What is the sum of the first five prime numbers?
  5. How many primes are there below 100?
  6. How many numbers from 1 to 12 are co-prime to 12?

Answers: 1) yes; 2) 101; 3) yes, they are consecutive; 4) 28; 5) 25; 6) 4 (1, 5, 7, 11).

Why Is This Topic Important?

  • Building block Every number is built from primes, which is the basis of HCF, LCM and factor counting.
  • Exam use Direct questions ask for prime counts, co-prime tests and prime checks.
  • Foundation Needed for remainder theorems in Fermat’s Little Theorem and Wilson’s Theorem Applications.
  • Link Helps with factors in Number of Factors, Sum of Factors and Product of Factors of a Number.

What Comes Next?

The next topic is Factorial Values and Number of Trailing Zeros in a Factorial, which uses prime factors to count trailing zeros in a factorial.

Key Terms and Formulas

  • Prime A natural number greater than 1 with exactly two factors
  • Composite A natural number with more than two factors
  • Co-prime Two numbers with highest common factor 1
  • Twin primes Primes that differ by 2
  • Euler totient Count of numbers up to n co-prime to n
  • Square root test Test primes up to the square root

Study this topic together with these linked topics from other subjects.

Exam Corner

Points to Remember

  • 25 primes lie below 100, and 2 is the only even prime.
  • 1 is neither prime nor composite.
  • Consecutive integers are co-prime.
  • Test primality by dividing by primes up to the square root.
  • Co-prime numbers need not be prime.

Do Not Confuse With

  • Prime vs co-prime Prime is a property of one number; co-prime is a property of a pair.
  • Composite vs not prime 1 is not prime and not composite.
  • Twin primes vs co-prime Twin primes differ by 2; co-prime pairs only share the factor 1.
  • Factor vs prime factor Prime factors are only the prime divisors.

Memory Hook

Two factors make a prime; a shared factor of 1 makes a co-prime pair.

GS Relevance

Prime and co-prime concepts are used in SSC CGL, CAT and CSAT for factor counting, HCF and LCM, and remainder questions.

Frequently Asked Questions

What is the difference between prime and composite numbers?

A prime number has exactly two factors, 1 and itself, while a composite number has more than two factors. For example, 7 is prime and 12 is composite. The number 1 is neither prime nor composite because it has only one factor, namely itself.

How do you check whether a number is prime?

To check whether a number is prime, divide it by every prime up to its square root. If none of them divides the number exactly, the number is prime. For example, 101 has square root about 10, and 2, 3, 5 and 7 do not divide it, so 101 is prime.

What are co-prime numbers?

Co-prime numbers are two numbers whose highest common factor is 1, so they share no prime factor. They do not have to be prime themselves. For example, 35 and 64 are co-prime because 35 is 5 times 7 and 64 is 2 to the power 6, with no common factor.

How many prime numbers are there below 100?

There are 25 prime numbers below 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 and 97. Of these, 10 lie between 50 and 100, and 2 is the only even prime among them.

How do you count the numbers up to n that are co-prime to n?

The count of numbers up to n that are co-prime to n is n multiplied by one minus one over each distinct prime factor of n. For 30, whose prime factors are 2, 3 and 5, the count is 30 times one half times two thirds times four fifths, which equals 8.

PYQ Practice — Statement Analysis

1 The number 1 is a prime number.
False

1 has only one factor, so it is neither prime nor composite.

2 2 is the only even prime number.
True

Every other even number is divisible by 2.

3 Co-prime numbers must both be prime.
False

8 and 15 are co-prime although neither is prime.

4 There are 25 prime numbers below 100.
True

They run from 2 to 97.

Share: