+91 9600 121 800

Back

Quant

Numbers

Factors & Remainders

ALL MODULES

CAT 2025 Lesson : Factors & Remainders - LCM with Remainders

3.3 LCM concept with Remainders

LCM is applied in the following three types of questions on remainders.

Type 1: When the remainder is the same (

\bm{r}

) for all the divisors.

These numbers are of the form

\bm{k} \ \times

LCM of divisors +

\bm{r}

, where

k

is a non–negative integer.

Smallest number that satisfies this is

\bm{r}

Example 14

What is the third smallest natural number that leaves the remainder of

1

when individually divided by

2

3

and

5

Solution

The smallest number that leaves a remainder of

1

1

itself.

LCM (

2

3

5

)

= 30

Second smallest number

= 1 \times 30 + 1 = 31

Third smallest number

= 2 \times 30 +1 = 61

Answer:

61

Type 2: When the differences between the respective divisors and remainders are equal.

These numbers are of the form

\bm{ k}

\times

LCM of divisors

-

\bm{d}

, where

k

is a non–negative integer and

d

is the common difference between divisors and remainders.

Smallest number that satisfies this is LCM of divisors

-

\bm{d}

Example 15

What is the smallest number which when divided by

24

36

and

48

leaves remainders of

11

23

and

35

respectively?

Solution

Difference between the respective divisors and remainders

= 13

\therefore

Smallest number

=

LCM(

24

36

48

)

-

13

= 144 - 13 = 131

Answer:

131

Type 3: Where Types

1

and

2

do not apply.

Express each of the numbers in the

dq

+

r

format. Substitute and find the smallest integral values of

q

that satisfy the expressions.

Let

x

be the smallest number that satisfies all the expressions.

These numbers are of the form

\bm{ k}

\times

LCM of divisors

+

\bm{x}

, where

k

is a non–negative integer.

Example 16

What is the smallest number that leaves remainders of

1

and

6

when divided by

3

and

14

respectively?

Solution

Let the number be

\bm{n}

. Where

a

and

b

are the respective quotients,

n = 3a + 1

n = 14b + 6

\therefore

3a

+

1 = 14b +6

Express one variable in terms of other.
(Note: As we have to find the value through trial and error, the lower the denominator, the easier it is.)

⇒

a = \dfrac{14b + 5}{3}

a

and

b

are quotients, both have to be non–negative integers.

b = 2

is the smallest value that makes (

14b

+

5

) divisible by

3

\therefore

the smallest number is when

b = 2

n = 14 \times 2 + 6 = 34

Answer:

34

Note: The number is of the format

c \ \times

LCM(

3

14

)

+ 34 = 42c + 34

.
Smallest number is when

c = 0

, which is

34

Example 17

What is the largest

3-

digit number that leaves remainders of

1

4

and

3

when divided by

3

5

and

11

respectively?

Solution

Let the number be

n

. Where a, b and c are the respective quotients,

n = 3a + 1 = 5b + 4 = 11c + 3

We first need to find the smallest value of n which satisfies the above conditions. We can find the smallest number only by taking

2

of them at a time. We start with the largest divisors and work downwards to keep the denominator small for ease of calculation.

5b + 4 = 11c + 3

⇒

b = \dfrac{11c - 1}{5}

For

b

to be an integer, smallest value of

c = 1

\therefore

Smallest remainder

= 11 \times 1 + 3 = 14

n = d \ \times

LCM (

5

11

)

+ 14 = \bm{55d + 14}

(where

d

is a positive integer)

3a + 1 = 55d + 14

⇒

a = \dfrac{55 d + 13}{3}

For

a

to be an integer, smallest value of

d = 2

\therefore

Smallest remainder

= 55 \times 2 + 14 = 124

n = e \ \times

LCM (

55

3

)

4+ 124 = \bm{165 e + 124}

All the conditions are satisfied here. The largest

3

digit number occurs when

e = 5

n = 165 \times 5 + 124 = 949

Answer:

949

3.4 Successive Division

Let's take a number,

250

, and find the remainders when

250

is successively divided by

3

4

and

6

. This simply means that the quotients are successively divided.

Note that once

250

is divided by

3

, the quotient

83

is then divided by

4

, whose quotient

20

is then divided by

6

\therefore

250

when successively divided by

3

4

and

6

leaves remainders of

1

3

and

2

respectively.

Questions of this kind will involve working backwards. The following examples has the divisors and remainders used above.

Let

\bm{x}

be the smallest number that we get from the above step.

These numbers are of the form

\bm{k \ \times}

Product of divisors

\bm{+\ x}

, where

k

is a non–negative integer.

Example 18

What are the smallest and

4

^th smallest natural numbers that leave remainders of

1

3

and

2

, when successively divided by

3

4

and

6

respectively?

Solution

The number has been successively divided

3

times. We start with the last division and work backwards.

Smallest number which when divided by

6

leaves a remainder of

2 = 2

Prior to division by

4

, the number

= 4 \times 2 + 3 = 11

Prior to division by

3

, the number

= 3 \times 11 + 1 = 34

Smallest number =

34

All such numbers are of the format

(3 \times 4 \times 6) k + 34 = 72k + 34

The

4

^th smallest number is when

k = 3

= 72 \times 3 + 34 = 250

Alternatively

1) We write the divisors in a row and their respective remainders below them.
2) We form two kinds of arrows - bottom right to top left arrows and top to bottom arrows.
3) We start from the right end and follow these operations - multiply along an upward arrow and add along a downward arrow.
4) The final result is the smallest number.

From the right,

1

^st up arrow ⇒

2 \times 4 = 8

;

1

^st down arrow ⇒

8 + 3 = 11

2

^nd up arrow ⇒

11 \times 3 = 33

;

2

^nd down arrow ⇒

33 + 1 = 34

\therefore

Smallest number

= 34

Product of divisors

= 3 \times 4 \times 6 = 72

Where the smallest number is

x

, these numbers are of the form

\bm{k \ \times}

Product of divisors

\bm{+ x}

2

^nd smallest number

= 1 \times 72 + 34

3

^rd smallest number

= 2 \times 72 + 34

4

^th smallest number

= 3 \times 72 + 34 = 250

Answer:

34

and

250

Want to read the full content

Unlock this content & enjoy all the features of the platform

Subscribe Now