# Concept of Successive Division

Suppose N is any number which is divided successively by 3 and 5, which means â€“ first, we divide N by 3 and then the quotient obtained is divided by 5.
E.g., Let us see the case when 50 is divided by 5 and 3 successively.

50 divided by 5 gives 10 as the quotient. Now, we will divide 10 by 3. It gives finally a quotient of 3 and remainder of 1.

Example

When a number N is divided successively by 3 and 5, remainder obtained are 1 and 2 respectively. What is the remainder when N is divided by 15?

Solution

It can be seen that we are required to calculate it from back-end.

Family of numbers which when divided by 5 gives remainder 2 = 5 S + 2

So, N = 3(5 S + 2) + 1 = 15 S + 7

Now, when N is divided by 15, remainder = 7

# Fermatâ€™s remainder therorem

Let P be a prime number and N be a number not divisible by P. Then the remainder obtained when A^{P}

^{-}

^{1}is divided by P is 1.

Example

What is the remainder when 2

^{100}is divided by 101?Solution

Since it satisfies the Fermatâ€™s theorem format, remainder = 1

# Eulerâ€™s theorem of remainder

Let*f*(

*n*) be the number of integers less than

*n*and co-prime with

*n*, then the remainder obtained when

*m*

^{f}^{(n)}is divided by

*n*is 1, where

*m*and

*n*are co-prime to each other.

As we can see:

*f*(2) = 1,

*f*(3) = 2,

*f*(4) = 2,

*f*(5) = 4

So, the remainder obtained when 8
Similarly, the remainder obtained when 12

^{f}^{(5) = 4 }is divided by 5 is 1. It can also be seen that the remainder obtained when any power of 8 divisible by 4 such as 8^{4}or 8^{8}or 8^{12}and so on will give the same remainder when divided by 5.^{f}^{(5) = 4 }is divided by 5 is 1; or, the remainder obtained when 8^{f}^{(7) = 6 }is divided by 7 is 1.

# Derivations

- will always give 1 as the remainder.

Example-1

What is the remainder when 9

^{100}is divided by 8?Solution

For A = 8, it satisfies the above condition.

So, remainder = 1

Alternatively, we can apply either cyclicity or theorem method to find the remainder. (Do this yourself).

- When
*N*is even, remainder is 1 and when*N*is odd, remainder is A itself.

Example-2

What is the remainder when 2

^{10}_{ }is divided by 3?Solution

Since here

*N*is even, so remainder = 1- i. (
*a*+^{n}*b*)^{n}_{ }is divisible by (*a*+*b*), if*n*is odd.

Extension of the above formula â€“ (*a*+^{n}*b*+^{n}*c*)^{n}_{ }is divisible by (*a*+*b*+*c*), if*n*is odd and a, b, c, are in arithmetic progression.

Similarly, the above situation can be extended for any number of terms.- (
*a*âˆ’^{n}*b*)^{n}_{ }is divisible by (*a*+*b*), if*n*is even. - (
*a*âˆ’^{n}*b*)^{n}_{ }is divisible by (*a*âˆ’*b*), if*n*is either odd or even.

- (

Example-3

What is the remainder when (15

^{23}+ 23^{23}) is divided by 19?**(CAT 2004, 2 marks)**Solution

It can be observed that (15

^{23}+ 23^{23}) is divisible by 38, so it will be divisible by 19 also. Hence, remainder = 0.Alternatively, this problem can be done either by cyclicity method or theorem method.

Example-4

What is the remainder when (16

^{3 }+ 17^{3 }+ 18^{3 }+ 19^{3}) is divided by 70?**(CAT 2005, 1 mark)**Solution

We know, this is a basic multiplication and division question. But using the above approach makes it a lot simple.

We know that (

*a**+*^{n}*b**) is divisible by (*^{n}*a*+*b*), if n is odd. Taking cue from this, we can say that (*a**+*^{n}*b**+*^{n}*c**) is divisible by (*^{n}*a*+*b*+*c*), if n is odd and similarly (*a**+*^{n}*b**+*^{n}*c**+*^{n}*d**) is divisible by (*^{n}*a*+*b*+*c*+*d*). Now 16 + 17 + 18 + 19 = 70, so remainder is zero. (As a, b, c, d are in AP)