# Notes: Concepts of Reminder for CAT Exam

Supposing a number N is divided by another number “x”; if the quotient obtained is “Q” and the remainder obtained is “R”,

then the number can be expressed as N=Qx+R

For example, suppose 8 is divided by 3

In this case, N=8, x=3. 3×2=6, which is 2 less than 8. hence Q=2 and R=(8-6)=2 Hence 8=2×3+2

**Basic Remainder Theorem**

Basic remainder theorem is based on product of individual remainders.

If R is the remainder of an expression( p*q*r)/X, and pR, qR and rR are the remainders when p,q and r are respectively divided by X,

then it can be said that ((p_{R} x q_{R} x r_{R} ))/X, will give the same remainder as given by (p*q*r)/X

Let us understand this with the help of an example

**Find the remainder when (361*363) is divided by 12.**

**Steps**

1) Take the product of individual remainders, i.e. 361/12|R =1 and 363/12|R= 3

2) Find the remainder when you divide that product by the number (361*363)/12|R= (1*3)/12|R. answer= 3

This is Basic Remainder theorem put across in Numbers

**Find the remainder when 10^6 is divided by 7 i.e. (10 ^{6}/7)_{R}.**

**Solution:**

10^{6}=10^{3}x10^{3}

Thus(10^{6}/7)R = (10^{3}/7 x 10^{3}/7)R = ((6 * 6)/7)R = (36/7)R = 1.

So the remainder is 1

Concept of negative remainder

The remainder obtained on division of a number N by a divisor X can be expressed in two ways as “R” and “X-R”

For example 10/11 remainder is +10 itself. It can also be written as 10-11= -1 Similarly, 32/10 remainder is +2 or -8

Let us express the solution for questions 31 above, in another way- based on the concept of negative remainder Thus(10^{6}/7)R = (10^{3}/7 x 10^{3}/7)R = ((-1 * -1)/7)R = (1/7)R = 1.

Remainder when the product of some numbers is divided by the requisite number is the product of individual remainders of the numbers-

This is Basic Remainder Theorem put across in words

Let us see why this happens

If the numbers N1,N2,N3 give remainders of R1,R2,R3 with quotients Q1,Q2,Q3 when divided by a common divisor D

N1=DQ1+R1 N2=DQ2+R2 N3=DQ3+R3

Multiplying=N1xN2xN3

=(DQ1+R1)x (DQ2+R2)x(DQ3+R3) = D(some number)+(R1xR2xR3) =first part is divisible by D,

hence you need to check for the individual remainders only.

## All possible types of Question on Reminder:

**What is the remainder when the product 1998 × 1999 × 2000 is divided by 7?**

Answer: the remainders when 1998, 1999, and 2000 are divided by 7 are 3, 4, and 5 respectively. Hence the final remainder is the remainder when the product 3 × 4 × 5 = 60 is divided by 7.

Answer = 4

**What is the remainder when 2**^{2004 }is divided by 7?

2 ^{2004 }is again a product (2 × 2 × 2… (2004 times)). Since 2 is a number less than 7 we try to convert the product into product of numbers higher than 7. Notice that 8 = 2 × 2 × 2. Therefore we convert the product in the following manner-

2 ^{2004 }= 8 ^{668 }= 8 × 8 × 8… (668 times).

The remainder when 8 is divided by 7 is 1.

Hence the remainder when 8 ^{668 }is divided by 7 is the remainder obtained when the product 1 × 1 × 1… is divided by 7

Answer = 1

**What is the remainder when 2**^{2006 }is divided by 7?

This problem is like the previous one, except that 2006 is not an exact multiple of 3 so we cannot convert it completely into the form 8 ^{x }. We will write it in following manner-

2 ^{2006 }= 8 ^{668 }× 4.

Now, 8 ^{668 }gives the remainder 1 when divided by 7 as we have seen in the previous problem. And 4 gives a remainder of 4 only when divided by 7. Hence the remainder when 2 ^{2006 }is divided by 7 is the remainder when the product 1 × 4 is divided by 7.

Answer = 4

**What is the remainder when 25**^{25 }is divided by 9?

Again 25 ^{25 }= (18 + 7) ^{25 }= (18 + 7)(18 + 7)…25 times = 18K + 7 ^{25}

Hence remainder when 25 ^{25 }is divided by 9 is the remainder when 7 ^{25 }is divided by 9.

Now 7 ^{25 }= 7 ^{3 }× 7 ^{3 }× 7 ^{3 }.. (8 times) × 7 = 343 × 343 × 343… (8 times) × 7.

The remainder when 343 is divided by 9 is 1 and the remainder when 7 is divided by 9 is 7.

Hence the remainder when 7 ^{25 }is divided by 9 is the remainder we obtain when the product 1 × 1 × 1… (8 times) × 7 is divided by 9. The remainder is 7 in this case. Hence the remainder when 25 ^{25 }is divided by 9 is 7.

**Some Special Cases:**

**2.1A When both the dividend and the divisor have a factor in common.**

Let N be a number and Q and R be the quotient and the remainder when N is divided by the divisor D.

Hence, N = Q × D + R.

Let N = k × A and D = k × B where k is the HCF of N and D and k > 1.

Hence kA = Q × kB + R.

Let Q _{1 }and R _{1 }be the quotient and the remainder when A is divided by B.

Hence A = B × Q _{1 }+ R _{1 }.

Putting the value of A in the previous equation and comparing we get-

k(B × Q _{1 }+ R _{1 }) = Q × kB + R –> R = kR _{1 }.

Hence to find the remainder when both the dividend and the divisor have a factor in common,

- Take out the common factor (i.e. divide the numbers by the common factor)
- Divide the resulting dividend (A) by resulting divisor (B) and find the remainder (R
_{1 }). - The real remainder R is this remainder R1 multiplied by the common factor (k).

**Examples**

**What the remainder when 2**^{96 }is divided by 96?

The common factor between 2 ^{96 }and 96 is 32 = 2 ^{5 }.

Removing 32 from the dividend and the divisor we get the numbers 2 ^{91 }and 3 respectively.

The remainder when 2 ^{91 }is divided by 3 is 2.

Hence the real remainder will be 2 multiplied by common factor 32.

Answer = 64

**2.1B THE CONCEPT OF NEGATIVE REMAINDER**

15 = 16 × 0 + 15 or

15 = 16 × 1 – 1.

The remainder when 15 is divided by 16 is 15 the first case and -1 in the second case.

Hence, the remainder when 15 is divided by 16 is 15 or -1.

–> When a number N < D gives a remainder R (= N) when divided by D, it gives a negative remainder of R – D.

For example, when a number gives a remainder of -2 with 23, it means that the number gives a remainder of 23 – 2 = 21 with 23.

**EXAMPLE**

**Find the remainder when 7**^{52 }is divided by 2402.

Answer: 7 ^{52 }= (7 ^{4 }) ^{13 }= (2401) ^{13 }= (2402 – 1) ^{13 }= 2402K + (-1) ^{13 }= 2402K – 1.

Hence, the remainder when 7 ^{52 }is divided by 2402 is equal to -1 or 2402 – 1 = 2401.

Answer: 2401.

**2 ****.1C ****When dividend is of the form a **^{n }**+ b **^{n }**or a **^{n }**– b **^{n }**:**

**EXAMPLES**

**What is the remainder when 3**^{444 }+ 4^{333 }is divided by 5?

Answer:

The dividend is in the form a ^{x }+ b ^{y }. We need to change it into the form a ^{n }+ b ^{n }.

3 ^{444 }+ 4 ^{333 }= (3 ^{4 }) ^{111 }+ (4 ^{3 }) ^{111 }.

Now (3 ^{4 }) ^{111 }+ (4 ^{3 }) ^{111 }will be divisible by 3 ^{4 }+ 4 ^{3 }= 81 + 64 = 145.

Since the number is divisible by 145 it will certainly be divisible by 5.

Hence, the remainder is 0.

**What is the remainder when (5555)**^{2222 }+ (2222)^{5555 }is divided by 7?

Answer:

The remainders when 5555 and 2222 are divided by 7 are 4 and 3 respectively.

Hence, the problem reduces to finding the remainder when (4) ^{2222 }+ (3) ^{5555 }is divided by 7.

Now (4) ^{2222 }+ (3) ^{5555 }= (4 ^{2 }) ^{1111 }+ (3 ^{5 }) ^{1111 }= (16) ^{1111 }+ (243) ^{1111 }.

Now (16) ^{1111 }+ (243) ^{1111 }is divisible by 16 + 243 or it is divisible by 259, which is a multiple of 7.

Hence the remainder when (5555) ^{2222 }+ (2222) ^{5555 }is divided by 7 is zero.

**20**^{2004 }+ 16^{2004 }– 3^{2004 }– 1 is divisible by:

(a) 317 (b) 323 (c) 253 (d) 91

Solution: 20 ^{2004 }+ 16 ^{2004 }– 3 ^{2004 }– 1 = (20 ^{2004 }– 3 ^{2004 }) + (16 ^{2004 }– 1 ^{2004 }).

Now 20 ^{2004 }– 3 ^{2004 }is divisible by 17 (Theorem 3) and 16 ^{2004 }– 1 ^{2004 }is divisible by 17 (Theorem 2).

Hence the complete expression is divisible by 17.

20 ^{2004 }+ 16 ^{2004 }– 3 ^{2004 }– 1 = (20 ^{2004 }– 1 ^{2004 }) + (16 ^{2004 }– 3 ^{2004 }).

Now 20 ^{2004 }– 1 ^{2004 }is divisible by 19 (Theorem 3) and 16 ^{2004 }– 3 ^{2004 }is divisible by 19 (Theorem 2).

Hence the complete expression is also divisible by 19.

Hence the complete expression is divisible by 17 × 19 = 323.

**2.1D ****When f(x) = a + bx + cx **^{2 }**+ dx **^{3 }**+… is divided by x – a**

**EXAMPLES**

**What is the remainder when x**^{3 }+ 2x^{2 }+ 5x + 3 is divided by x + 1?

Answer: The remainder when the expression is divided by (x – (-1)) will be f(-1).

Remainder = (-1) ^{3 }+ 2(-1) ^{2 }+ 5(-1) + 3 = -1

**If 2x**^{3 }-3x^{2 }+ 4x + c is divisible by x – 1, find the value of c.

Since the expression is divisible by x – 1, the remainder f(1) should be equal to zero.

Or 2 – 3 + 4 + c = 0, or c = -3.

**2 ****.1E ****Fermat’s Theorem**

**EXAMPLE**

**What is the remainder when n**^{7 }– n is divided by 42?

Answer: Since 7 is prime, n ^{7 }– n is divisible by 7.

n ^{7 }– n = n(n ^{6 }– 1) = n (n + 1)(n – 1)(n ^{4 }+ n ^{2 }+ 1)

Now (n – 1)(n)(n + 1) is divisible by 3! = 6

Hence n ^{7 }– n is divisible by 6 x 7 = 42.

Hence the remainder is 0.

**2.1F ****Wilson’****s Theorem**

**EXAMPLE**

**Find the remainder when 16! Is divided by 17.**

16! = (16! + 1) -1 = (16! + 1) + 16 – 17

Every term except 16 is divisible by 17 in the above expression. Hence the remainder = the remainder obtained when 16 is divided by 17 = 16

Answer = 16

**2.1G TO FIND THE NUMBER OF NUMBERS, THAT ARE LESS THAN OR EQUAL TO A CERTAIN NATURAL NUMBER N, AND THAT ARE DIVISIBLE BY A CERTAIN INTEGER**

To find the number of numbers, less than or equal to n, and that are divisible by a certain integer p, we divide n by p. The quotient of the division gives us the number of numbers divisible by p and less than or equal to n.

**EXAMPLE**

**14. How many numbers less than 400 are divisible by 12?**

Answer: Dividing 400 by 12, we get the quotient as 33. Hence the number of numbers that are below 400 and divisible by 12 is 33.

**15. How many numbers between 1 and 400, both included, are not divisible either by 3 or 5?**

Answer: We first find the numbers that are divisible by 3 or 5. Dividing 400 by 3 and 5, we get the quotients as 133 and 80 respectively. Among these numbers divisible by 3 and 5, there are also numbers which are divisible both by 3 and 5 i.e. divisible by 3 x 5 = 15. We have counted these numbers twice. Dividing 400 by 15, we get the quotient as 26.

Hence the number divisible by 3 or 5 = 133 + 80 – 26 = 187

Hence, the numbers not divisible by 3 or 5 are = 400 – 187 = 213.

**16. How many numbers between 1 and 1200, both included, are not divisible by any of the numbers 2, 3 and 5?**

Answer: as in the previous example, we first find the number of numbers divisible by 2, 3, or 5. from set theory we have

n(AUBUC) = n(A) + n(B) + n(C) – n(A intersectn B) – n(B intersectn C) – n(A intersectn C) + n(A intersectn B intersectn C)

n(2U3U5) = n(2) + n(3) + n(5) – n(6) – n(15) – n(10) + n(30)

–> n(2U3U5) = 600 + 400 + 240 – 200 – 80 – 120 + 40 = 880

Hence number of numbers not divisible by any of the numbers 2, 3, and 5

= 1200 – 880 = 320.