Free CAT library

Successive Division & Ladder Algorithms

Master the mechanics of successive division where the quotient of one step becomes the dividend of the next, and reverse-engineer the original number.

1. The Story & Mental Model

Imagine a relay race of division.

In normal division, you divide a number NN by a divisor dd, get a quotient qq and a remainder rr. The game ends there.

In successive division, the quotient qq grabs the baton and keeps running! The quotient qq becomes the new starting number for the next divisor.

Suppose a number is successively divided by 4, then 5.

  1. Divide NN by 4   ⟹  \implies you get Quotient Q1Q_1 and Remainder R1R_1.

  2. Take Q1Q_1, divide it by 5   ⟹  \implies you get Quotient Q2Q_2 and Remainder R2R_2.

To reconstruct the original number NN, you have to walk backwards. You start with the final quotient, multiply by the last divisor, add the last remainder, and pass that result backwards up the ladder until you reach NN.

2. The CAT Question Blueprint

This is a niche but highly standardized topic. The questions will look exactly like:

  • "A number when successively divided by 3, 5, and 8 leaves remainders 1, 4, and 7 respectively. Find the least such number."

  • "If the same number is divided by the same divisors but in reverse order, what will the remainders be?"

  • "Find the general form of all such numbers."

3. Core Concepts, Formulae & Derivations

A. The Ladder Method (Reconstruction)

To find the smallest original number NN given divisors d1,d2,d3d_1, d_2, d_3 and remainders r1,r2,r3r_1, r_2, r_3:

  1. Assume the final quotient is 00 (this yields the absolutely smallest valid number).

  2. Start from the bottom:

    Quotient Q2=(0×d3)+r3=r3Q_2 = (0 \times d_3) + r_3 = r_3.

  3. Step up:

    Quotient Q1=(Q2×d2)+r2Q_1 = (Q_2 \times d_2) + r_2.

  4. Final step:

    Number Nmin=(Q1×d1)+r1N_{\text{min}} = (Q_1 \times d_1) + r_1.

Visualizing the Ladder:

DivisorDividendRemainder
d1d_1NNr1r_1
d2d_2Q1Q_1r2r_2
d3d_3Q2Q_2r3r_3
0

(Multiply left-down, add right: Q2=0×d3+r3Q_2 = 0 \times d_3 + r_3. Then Q1=Q2×d2+r2Q_1 = Q_2 \times d_2 + r_2. Then N=Q1×d1+r1N = Q_1 \times d_1 + r_1).

B. The General Form

Once you find the smallest number NminN_{\text{min}}, the general form of all such numbers is:

N=k⋅(d1×d2×d3)+NminN = k \cdot (d_1 \times d_2 \times d_3) + N_{\text{min}}

where kk is any whole number (0,1,2,…0, 1, 2, \dots).

C. Reversing the Divisors

If the question asks for remainders when divisors are reversed (e.g., divided by 8, then 5, then 3), you MUST find NminN_{\text{min}} first, and then perform actual successive division using the new order of divisors. You cannot just reverse the remainders!

4. Common Pitfalls & Speed Shortcuts

  • Pitfall: Assuming "successive division" just means dividing the original number NN multiple times. No! That's LCM/HCF model territory. Successive division strictly means dividing the quotients.

  • Shortcut: For finding NminN_{\text{min}}, you can use this linear formula instead of drawing the ladder:

    Nmin=r1+d1×r2+d1×d2×r3+…N_{\text{min}} = r_1 + d_1 \times r_2 + d_1 \times d_2 \times r_3 + \dots

    (Notice how the remainders are multiplied by the accumulation of previous divisors).

Formulas

Linear Minimum Number

Nmin=r1+d1r2+d1d2r3N_{\text{min}} = r_1 + d_1 r_2 + d_1 d_2 r_3

Lightning fast alternative to the ladder method.
General Form

N=k(d1d2d3)+NminN = k(d_1 d_2 d_3) + N_{\text{min}}

Adds the product of all divisors to scale up.

Traps and tips

  • Always assume the final quotient is 0 to find the least possible number.
  • Do not confuse successive division with simultaneous division (LCM models). Look for the word 'successively'.
  • When divisors are reversed, you must re-calculate. The remainders do not simply reverse.

Solved examples

The Basic Ladder

A number when successively divided by 4, 5, and 6 leaves remainders 2, 3, and 4 respectively. Find the least such number.

Show solution

Let's use the Ladder Method. Assume the final quotient is 0.

Divisors: 4, 5, 6.

Remainders: 2, 3, 4.

Step 1 (Bottom): Q2=(0×6)+4=4Q_2 = (0 \times 6) + 4 = 4.

Step 2 (Middle): Q1=(Q2×5)+3=(4×5)+3=23Q_1 = (Q_2 \times 5) + 3 = (4 \times 5) + 3 = 23.

Step 3 (Top): N=(Q1×4)+2=(23×4)+2=92+2=94N = (Q_1 \times 4) + 2 = (23 \times 4) + 2 = 92 + 2 = 94.

The least such number is 94.

Let's verify using the Linear Shortcut:

Nmin=r1+d1×r2+d1×d2×r3N_{\text{min}} = r_1 + d_1 \times r_2 + d_1 \times d_2 \times r_3

Nmin=2+(4×3)+(4×5×4)N_{\text{min}} = 2 + (4 \times 3) + (4 \times 5 \times 4)

Nmin=2+12+80=94N_{\text{min}} = 2 + 12 + 80 = 94.

Both methods yield 94 effortlessly.

Takeaway: The linear formula N min = r1 + d1 r2 + d1 d2 r3 is the fastest way to solve standard successive division problems.

The Reverse Run

A number when successively divided by 3, 4, and 7 leaves remainders 2, 1, and 4 respectively. What will be the remainders if the same number is divided successively by 7, 4, and 3?

Show solution

First, find the least original number NminN_{\text{min}}.

Using the shortcut: Nmin=r1+d1r2+d1d2r3N_{\text{min}} = r_1 + d_1r_2 + d_1d_2r_3.

Here, d1=3,d2=4,d3=7d_1=3, d_2=4, d_3=7 and r1=2,r2=1,r3=4r_1=2, r_2=1, r_3=4.

Nmin=2+(3×1)+(3×4×4)N_{\text{min}} = 2 + (3 \times 1) + (3 \times 4 \times 4)

Nmin=2+3+48=53N_{\text{min}} = 2 + 3 + 48 = 53.

Now, perform successive division on 53 using the reversed divisors: 7, 4, 3.

  1. Divide 53 by 7:

    53/7=753 / 7 = 7 with remainder 4.

    New dividend is 7.

  2. Divide 7 by 4:

    7/4=17 / 4 = 1 with remainder 3.

    New dividend is 1.

  3. Divide 1 by 3:

    1/3=01 / 3 = 0 with remainder 1.

The remainders in the reverse order are 4, 3, and 1.

Takeaway: Never assume the remainders reverse when the divisors reverse. You must calculate N min and manually divide again.

Scaling the Multiples

A number when successively divided by 5 and 6 leaves remainders 3 and 2 respectively. What is the largest 3-digit number that satisfies this condition?

Show solution

First, find the least such number NminN_{\text{min}}.

Divisors: 5, 6.

Remainders: 3, 2.

Nmin=r1+d1r2=3+(5×2)=13N_{\text{min}} = r_1 + d_1r_2 = 3 + (5 \times 2) = 13.

Next, find the general form of the number.

The product of divisors is 5×6=305 \times 6 = 30.

The general form is N=30k+13N = 30k + 13.

We need the largest 3-digit number, so N≤999N \le 999.

30k+13≤99930k + 13 \le 999

30k≤98630k \le 986

k≤986/30=32.86k \le 986 / 30 = 32.86.

The largest integer value for kk is 32.

Substitute k=32k = 32 into the general form:

N=30(32)+13=960+13=973N = 30(32) + 13 = 960 + 13 = 973.

The largest 3-digit number is 973.

Takeaway: The interval between valid numbers in successive division is always the product of all the divisors (d1 d2 d3...).

The True Remainders

A number is successively divided by 6, 7, and 8, leaving remainders 3, 4, and 5. What would be the remainder if the number was directly divided by 336?

Show solution

Let's find the general form of the number.

First, find NminN_{\text{min}} using the linear formula:

Nmin=r1+d1r2+d1d2r3N_{\text{min}} = r_1 + d_1r_2 + d_1d_2r_3

Nmin=3+(6×4)+(6×7×5)N_{\text{min}} = 3 + (6 \times 4) + (6 \times 7 \times 5)

Nmin=3+24+210=237N_{\text{min}} = 3 + 24 + 210 = 237.

The general form is N=k(6×7×8)+237N = k(6 \times 7 \times 8) + 237.

N=336k+237N = 336k + 237.

The question asks for the remainder when the number is divided by 336.

By looking at the general form N=336k+237N = 336k + 237, it is obvious that any such number, when divided by 336, will leave a perfect quotient of kk and a remainder of 237.

So, the remainder is simply NminN_{\text{min}}, which is 237.

Takeaway: The remainder when dividing the original number by the product of all divisors is exactly equal to the N min calculated from the ladder.

Final Quotient Non-Zero

A number when successively divided by 2, 3, and 5 leaves remainders 1, 2, and 3. If the final quotient is 4, what is the number?

Show solution

Usually we assume the final quotient is 0 to find the minimum number. Here, the final quotient is explicitly given as 4.

Let's use the ladder method.

Divisors: 2, 3, 5.

Remainders: 1, 2, 3.

Final Quotient: 4.

Step 1 (Bottom): Q2=(4×5)+3=23Q_2 = (4 \times 5) + 3 = 23.

Step 2 (Middle): Q1=(23×3)+2=69+2=71Q_1 = (23 \times 3) + 2 = 69 + 2 = 71.

Step 3 (Top): N=(71×2)+1=142+1=143N = (71 \times 2) + 1 = 142 + 1 = 143.

The number is 143.

(Check: 143/2=71143/2 = 71 R1; 71/3=2371/3 = 23 R2; 23/5=423/5 = 4 R3. Correct).

Takeaway: If the final quotient is specified, simply substitute it instead of 0 at the bottom of the ladder and climb up normally.

Algebraic Successive Division

When NN is successively divided by xx and yy, the remainders are aa and bb. Express the minimum value of NN algebraically.

Show solution

This is a straight application of the linear formula or ladder method.

Divisors: x,yx, y

Remainders: a,ba, b

Final Quotient: 00 (for minimum value).

Ladder:

Q1=(0×y)+b=bQ_1 = (0 \times y) + b = b.

N=(Q1×x)+a=(b×x)+a=bx+aN = (Q_1 \times x) + a = (b \times x) + a = bx + a.

Using the linear formula:

Nmin=r1+d1r2N_{\text{min}} = r_1 + d_1r_2

Here r1=ar_1 = a, d1=xd_1 = x, r2=br_2 = b.

Nmin=a+x(b)=bx+aN_{\text{min}} = a + x(b) = bx + a.

The algebraic expression is bx+abx + a.

Takeaway: The structural logic of successive division applies seamlessly to variables. N min for two layers is simply (second remainder first divisor) + first remainder.

Practice questions

Question 1 · CAT Level

A positive integer NN when divided successively by 4,5,4, 5, and 66 leaves remainders 2,3,2, 3, and 44 respectively. If the order of the divisors is reversed (i.e., NN is divided successively by 6,5,6, 5, and 44), what are the respective remainders obtained?

  1. A

    4, 0, 3

  2. B

    4, 1, 2

  3. C

    3, 2, 1

  4. D

    4, 3, 2

Show answer and explanation

Answer: (A) 4, 0, 3

By the ladder algorithm for successive division, the number NN can be expressed as:

N=4[5(6q+4)+3]+2=4[30q+23]+2=120q+94N = 4[5(6q + 4) + 3] + 2 = 4[30q + 23] + 2 = 120q + 94, where q≥0q \ge 0 is the final quotient.

The minimum positive value occurs at q=0q = 0, giving N=94N = 94.

Now divide N=94N = 94 successively by the reversed sequence of divisors (6,5,4)(6, 5, 4):

1)1) 94=6(15)+494 = 6(15) + 4 (remainder 44); 2)2) 15=5(3)+015 = 5(3) + 0 (remainder 00); 3)3) 3=4(0)+33 = 4(0) + 3 (remainder 33).

For any higher value N=120q+94N = 120q + 94, the remainders remain identically (4,0,3)(4, 0, 3) because 120120 is divisible by 6×5×46 \times 5 \times 4.

Hence, the respective remainders are 4,0,34, 0, 3.

Question 2 · CAT Level

A positive integer NN when divided successively by 3,5,3, 5, and 77 leaves remainders 1,2,1, 2, and 44 respectively. If NN is a four-digit number strictly between 20002000 and 30003000 and is completely divisible by 1313, what is the sum of the digits of NN?

  1. A

    18

  2. B

    20

  3. C

    22

  4. D

    25

Show answer and explanation

Answer: (C) 22

Unfolding the successive division ladder: N=3[5(7q+4)+2]+1=3[35q+22]+1=105q+67N = 3[5(7q + 4) + 2] + 1 = 3[35q + 22] + 1 = 105q + 67.

We are given that NN is a multiple of 1313, so 105q+67≡0(mod13)105q + 67 \equiv 0 \pmod{13}.

Reducing modulo 1313: 105=13(8)+1≡1105 = 13(8) + 1 \equiv 1, and 67=13(5)+2≡267 = 13(5) + 2 \equiv 2.

The congruence becomes q+2≡0(mod13)  ⟹  q≡11(mod13)q + 2 \equiv 0 \pmod{13} \implies q \equiv 11 \pmod{13}.

Thus q=13k+11q = 13k + 11, which gives N=105(13k+11)+67=1365k+1155+67=1365k+1222N = 105(13k + 11) + 67 = 1365k + 1155 + 67 = 1365k + 1222.

We are given that 2000<N<30002000 < N < 3000.

For k=1k = 1: N=1365(1)+1222=2587N = 1365(1) + 1222 = 2587 (which lies in (2000,3000)(2000, 3000)).

Summing the digits of N=2587N = 2587: 2+5+8+7=222 + 5 + 8 + 7 = 22.

Question 3 · CAT Level

A positive integer NN when divided successively by 5,7,5, 7, and 88 leaves remainders 3,4,3, 4, and 55 respectively. What is the remainder when NN is divided directly by 140140?

  1. A

    38

  2. B

    48

  3. C

    58

  4. D

    68

Show answer and explanation

Answer: (C) 58

Write out the algebraic structure of the successive division:

N=5[7(8q+5)+4]+3N = 5[7(8q + 5) + 4] + 3.

Expanding step-by-step gives 7(8q+5)+4=56q+397(8q + 5) + 4 = 56q + 39, so N=5(56q+39)+3=280q+198N = 5(56q + 39) + 3 = 280q + 198.

We wish to find the remainder when NN is divided directly by 140140.

Since 280280 is an exact multiple of 140140 (280=140×2280 = 140 \times 2), the term 280q280q contributes 00 to the remainder.

Therefore, N(mod140)=198(mod140)N \pmod{140} = 198 \pmod{140}.

Dividing 198198 by 140140: 198=140×1+58198 = 140 \times 1 + 58, giving a unique remainder of 5858.

Question 4 · CAT Level

Let NN be the smallest positive integer that leaves remainders 2,3,2, 3, and 44 when divided simultaneously by 5,6,5, 6, and 77 respectively. Let MM be the smallest positive integer that leaves remainders 2,3,2, 3, and 44 when divided successively by 5,6,5, 6, and 77 respectively. What is ∣N−M∣|N - M|?

  1. A

    55

  2. B

    70

  3. C

    85

  4. D

    100

Show answer and explanation

Answer: (B) 70

For simultaneous division, the difference is constant: 5−2=6−3=7−4=35 - 2 = 6 - 3 = 7 - 4 = 3.

Thus N=k×lcm(5,6,7)−3=210k−3N = k \times \text{lcm}(5, 6, 7) - 3 = 210k - 3.

The smallest positive integer is obtained for k=1k = 1: N=210(1)−3=207N = 210(1) - 3 = 207.

For successive division, unfolding the ladder gives M=5[6(7q+4)+3]+2M = 5[6(7q + 4) + 3] + 2 with final quotient q≥0q \ge 0.

The smallest positive integer occurs at q=0q = 0: M=5[6(4)+3]+2=5(27)+2=137M = 5[6(4) + 3] + 2 = 5(27) + 2 = 137.

Therefore, ∣N−M∣=∣207−137∣=70|N - M| = |207 - 137| = 70.

Question 5 · CAT Level

A positive integer NN when divided successively by 2,3,4,2, 3, 4, and 55 leaves remainders 1,2,3,1, 2, 3, and 44 respectively. How many three-digit integers NN satisfy this property?

  1. A

    6

  2. B

    7

  3. C

    8

  4. D

    9

Show answer and explanation

Answer: (C) 8

Express the successive division recursively: N=2[3[4(5q+4)+3]+2]+1N = 2[3[4(5q + 4) + 3] + 2] + 1 with q≥0q \ge 0.

Unfolding step-by-step from inside out:

4(5q+4)+3=20q+194(5q + 4) + 3 = 20q + 19, and 3(20q+19)+2=60q+593(20q + 19) + 2 = 60q + 59.

Thus N=2(60q+59)+1=120q+119N = 2(60q + 59) + 1 = 120q + 119.

For NN to be a three-digit integer, 100≤120q+119≤999  ⟹  0≤120q≤880100 \le 120q + 119 \le 999 \implies 0 \le 120q \le 880.

Since qq is an integer, 0≤q≤⌊880/120⌋=70 \le q \le \lfloor 880/120 \rfloor = 7, giving exactly 88 valid values (q∈{0,1,…,7}q \in \{0, 1, \dots, 7\}).

Study this concept with interactive practice in PrepSoc.

Open the concept library