+91 9600 121 800

Back

Quant

Numbers

Number Theory

ALL MODULES

CAT 2025 Lesson : Number Theory - Prime Numbers

5. Prime and Composite numbers

5.1 Prime numbers

Prime numbers are those natural numbers that can be perfectly divided by exactly two positive integers,

1

and the number itself. In other words, prime numbers have exactly two factors. The increasing sequence of prime numbers is

2

3

5

7

11

13

17

19 ...

The number

1

is neither prime nor composite.

Some key points to note here are:

1) No pattern has been established for the occurrence of prime numbers.
2) All prime numbers are odd numbers, with the exception of

2

.
3) All prime numbers except

2

and

5

end with the digits

1

3

7

9

.
4) For ease in exams, note that there are

15

prime numbers less than

50

and

25

prime numbers less than

100

.
5) All prime numbers, other than

2

and

3

, are in the form

(6k + 1)

(6k - 1)

, where k is a positive integer.

5.2 Composite numbers

Composite numbers are natural numbers that have more than two factors. These are numbers formed when two or more prime numbers are multiplied.

4=2 \times 2

105=3 \times 5 \times 7

. Composite numbers can be odd or even (eg.,

4

9

)

5.3 Test for Prime

To check whether a number is prime or not:

Step 1: Calculate the square root of the number.
Step 2: If the square root is an integer, then the number is not prime. If not,
Step 3: Determine all prime numbers less than or equal to the square root
Step 4: Check if any of these prime numbers perfectly divide the number
Step 5: If none of them divide the number, then the number is prime, else the number is composite.

Example 15

Which of

143

323

and

331

are prime numbers?

Solution

\sqrt{143} \lt \sqrt{144} = 12

Prime numbers less than

12

are

2

3

5

7

and

11

\bm{143}

is divisible by

11

and

\therefore

not prime.

\sqrt{323} \lt \sqrt{324} = 18

Prime numbers less than

18

are

2

3

5

7

11

13

and

17

\bm{323}

is divisible by

17

and

\therefore

not prime.

\sqrt{331} \lt \sqrt{361} = 19

Prime numbers less than

19

are

2

3

5

7

11

13

and

17

\bm{331}

is not divisible by any of these and

\therefore

is prime.

Answer:

331

only

5.4 Co-prime Numbers

When two numbers do not have any common factors except for

1

, they are said to be co-primes as they are prime relative to each other. For instance,

4

and

9

, though composite numbers, are co-prime numbers as they do not have any common factors aside from

1

Example 16

Which of the following options have a pair of numbers that are co-prime?

(1)

12

and

21

(2)

18

and

49

(3)

24

and

38

(4)

37

and

111

Solution

Co-primes do not have any common factor.

Option 1:

3

is a common factor.
Option 2: No common factor.

\therefore

Co-prime

Option 3:

2

is a common factor.

Option 4:

37

is a common factor.

Answer: (2)

18

and

49

Want to read the full content

Unlock this content & enjoy all the features of the platform

Subscribe Now