+91 9600 121 800

Plans

Dashboard

Daily & Speed

Quant

Verbal

DILR

Compete

Free Stuff

calendarBack
Quant

/

Numbers

/

Factors & Remainders

Factors And Remainders

MODULES

HCF & LCM
Number of Factors
HCF with Remainders
LCM with Remainders
Operations on Remainders
Euler & Fermat
Special Types
Past Questions

CONCEPTS & CHEATSHEET

Concept Revision Video

SPEED CONCEPTS

Factors & Remainders 1
-/10
Factors & Remainders 2
-/10
Factors & Remainders 3
-/10
Factors & Remainders 4
-/10

PRACTICE

Factors & Remainders : Level 1
-/15
Factors & Remainders : Level 2
-/15
Factors & Remainders : Level 3
-/10
ALL MODULES

CAT 2025 Lesson : Factors & Remainders - LCM with Remainders

bookmarked

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 (r\bm{r}r) for all the divisors.

These numbers are of the form k ×\bm{k} \ \timesk × LCM of divisors + r\bm{r}r, where kkk is a non–negative integer.

Smallest number that satisfies this is r\bm{r}r.

Example 14

What is the third smallest natural number that leaves the remainder of 111 when individually divided by 222, 333 and 555?

Solution

The smallest number that leaves a remainder of 111 is 111 itself.

LCM (222, 333, 555) =30= 30=30

Second smallest number =1×30+1=31= 1 \times 30 + 1 = 31=1×30+1=31

Third smallest number =2×30+1=61= 2 \times 30 +1 = 61=2×30+1=61

Answer: 616161

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

These numbers are of the form k\bm{ k}k ×\times× LCM of divisors −-− d\bm{d}d, where kkk is a non–negative integer and ddd is the common difference between divisors and remainders.

Smallest number that satisfies this is LCM of divisors −-− d\bm{d}d .

Example 15

What is the smallest number which when divided by 242424, 363636 and 484848 leaves remainders of 111111, 232323 and 353535 respectively?

Solution

Difference between the respective divisors and remainders =13= 13=13

∴\therefore∴ Smallest number === LCM(242424, 363636, 484848) −-− 131313
=144−13=131= 144 - 13 = 131=144−13=131

Answer: 131131131

Type 3: Where Types 111 and 222 do not apply.

Express each of the numbers in the dqdqdq +++ rrr format. Substitute and find the smallest integral values of qqq that satisfy the expressions.

Let xxx be the smallest number that satisfies all the expressions.

These numbers are of the form k\bm{ k}k ×\times× LCM of divisors +++ x\bm{x}x , where kkk is a non–negative integer.

Example 16

What is the smallest number that leaves remainders of 111 and 666 when divided by 333 and 141414 respectively?

Solution

Let the number be n\bm{n}n. Where aaa and bbb are the respective quotients,
n=3a+1n = 3a + 1n=3a+1
n=14b+6n = 14b + 6n=14b+6
∴\therefore∴ 3a3a3a +++ 1=14b+61 = 14b +61=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=14b+53a = \dfrac{14b + 5}{3}a=314b+5​

As aaa and bbb are quotients, both have to be non–negative integers.
b=2b = 2b=2 is the smallest value that makes (14b14b14b +++ 555) divisible by 333.

∴\therefore∴ the smallest number is when b=2b = 2b=2.
n=14×2+6=34n = 14 \times 2 + 6 = 34n=14×2+6=34

Answer: 343434

Note: The number is of the format c ×c \ \timesc × LCM(333, 141414) +34=42c+34+ 34 = 42c + 34+34=42c+34.
Smallest number is when c=0c = 0c=0, which is 343434.

Example 17

What is the largest 3−3-3−digit number that leaves remainders of 111, 444 and 333 when divided by 333, 555 and 111111 respectively?

Solution

Let the number be nnn. Where a, b and c are the respective quotients,
n=3a+1=5b+4=11c+3n = 3a + 1 = 5b + 4 = 11c + 3n=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 222 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+35b + 4 = 11c + 35b+4=11c+3 ⇒ b=11c−15b = \dfrac{11c - 1}{5}b=511c−1​

For bbb to be an integer, smallest value of c=1c = 1c=1
∴\therefore∴ Smallest remainder =11×1+3=14= 11 \times 1 + 3 = 14=11×1+3=14

n=d ×n = d \ \timesn=d × LCM (555, 111111) +14=55d+14+ 14 = \bm{55d + 14}+14=55d+14(where ddd is a positive integer)

3a+1=55d+143a + 1 = 55d + 143a+1=55d+14 ⇒ a=55d+133a = \dfrac{55 d + 13}{3}a=355d+13​

For aaa to be an integer, smallest value of d=2d = 2d=2
∴\therefore∴ Smallest remainder =55×2+14=124= 55 \times 2 + 14 = 124=55×2+14=124
n=e ×n = e \ \timesn=e × LCM (555555, 333) 4+124=165e+1244+ 124 = \bm{165 e + 124}4+124=165e+124

All the conditions are satisfied here. The largest 333 digit number occurs when e=5e = 5e=5.
n=165×5+124=949n = 165 \times 5 + 124 = 949n=165×5+124=949

Answer: 949949949

3.4 Successive Division

Let's take a number, 250250250, and find the remainders when 250250250 is successively divided by 333, 444 and 666. This simply means that the quotients are successively divided.



Note that once 250250250 is divided by 333, the quotient 838383 is then divided by 444, whose quotient 202020 is then divided by 666.

∴\therefore∴ 250250250 when successively divided by 333, 444 and 666 leaves remainders of 111, 333 and 222 respectively.

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

Let x\bm{x}x be the smallest number that we get from the above step.

These numbers are of the form k ×\bm{k \ \times}k × Product of divisors + x\bm{+\ x}+ x, where kkk is a non–negative integer.

Example 18

What are the smallest and 444th smallest natural numbers that leave remainders of 111, 333 and 222, when successively divided by 333, 444 and 666 respectively?

Solution

The number has been successively divided 333 times. We start with the last division and work backwards.

Smallest number which when divided by 666 leaves a remainder of 2=22 = 22=2

Prior to division by 444, the number =4×2+3=11= 4 \times 2 + 3 = 11=4×2+3=11

Prior to division by 333, the number =3×11+1=34= 3 \times 11 + 1 = 34=3×11+1=34

Smallest number = 343434

All such numbers are of the format (3×4×6)k+34=72k+34(3 \times 4 \times 6) k + 34 = 72k + 34(3×4×6)k+34=72k+34

The 444th smallest number is when k=3k = 3k=3,
=72×3+34=250= 72 \times 3 + 34 = 250=72×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,
111st up arrow ⇒ 2×4=82 \times 4 = 82×4=8; 111st down arrow ⇒ 8+3=118 + 3 = 118+3=11

222nd up arrow ⇒ 11×3=3311 \times 3 = 3311×3=33; 222nd down arrow ⇒ 33+1=3433 + 1 = 3433+1=34

∴\therefore∴ Smallest number =34= 34=34

Product of divisors =3×4×6=72= 3 \times 4 \times 6 = 72=3×4×6=72

Where the smallest number is xxx, these numbers are of the form k ×\bm{k \ \times}k × Product of divisors +x\bm{+ x}+x.

222nd smallest number =1×72+34= 1 \times 72 + 34=1×72+34
333rd smallest number =2×72+34= 2 \times 72 + 34=2×72+34
444th smallest number =3×72+34=250= 3 \times 72 + 34 = 250=3×72+34=250

Answer: 343434 and 250250250

Want to read the full content

Unlock this content & enjoy all the features of the platform

Subscribe Now arrow-right
videovideo-lock