Remainder Theorem

Hello Reader,

The content below was provided at TG (www.totalgadha.com). I felt like sharing this awesome concept on Remainder Theorem so that many other CAT/MBA aspirants can benefit from it.

Hats off to TG for such a valuable Article !!!

Suppose the numbers N ₁ , N ₂ , N ₃ … give quotients Q ₁ , Q ₂ , Q ₃ … and remainders R ₁ , R ₂ , R ₃ ..., respectively, when divided by a common divisor D.

Therefore N ₁ = D × Q ₁ + R ₁ ,

N ₂ = D × Q ₂ + R ₂ ,

N ₃ = D × Q ₃ + R ₃ .. and so on.

Let P be the product of N ₁ , N ₂ , N ₃ …

Therefore, P = N ₁ N ₂ N ₃ ..

= (D × Q ₁ + R ₁ )(D × Q ₂ + R ₂ )(D × Q ₃ + R ₃ )..

= D × K + R ₁ R ₂ R ₃ ... where K is some number ---- (1)

In the above equation, only the product R ₁ R ₂ R ₃ … is free of D, therefore the remainder when P is divided by D is the remainder when the product R ₁ R ₂ R ₃ … is divided by D.

Let S be the sum of N ₁ , N ₂ , N ₃ …

Therefore, S = (N ₁ ) + (N ₂ ) + (N ₃ ) +...

= (D × Q ₁ + R ₁ ) + (D × Q ₂ + R ₂ ) + (D × Q ₃ + R ₃ )..

= D × K + R ₁ + R ₂ + R ₃ … where K is some number--- (2)

Hence the remainder when S is divided by D is the remainder when R ₁ + R ₂ + R ₃ is divided by D.

Examples:

1. 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

2. What is the remainder when 2 ²⁰⁰⁴ is divided by 7?

2 ²⁰⁰⁴ 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 ²⁰⁰⁴ = 8 ⁶⁶⁸ = 8 × 8 × 8... (668 times).

The remainder when 8 is divided by 7 is 1.

Hence the remainder when 8 ⁶⁶⁸ is divided by 7 is the remainder obtained when the product 1 × 1 × 1... is divided by 7

Answer = 1

3. What is the remainder when 2 ²⁰⁰⁶ 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 ²⁰⁰⁶ = 8 ⁶⁶⁸ × 4.

Now, 8 ⁶⁶⁸ 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 ²⁰⁰⁶ is divided by 7 is the remainder when the product 1 × 4 is divided by 7.

Answer = 4

4. What is the remainder when 25 ²⁵ is divided by 9?

Again 25 ²⁵ = (18 + 7) ²⁵ = (18 + 7)(18 + 7)...25 times = 18K + 7 ²⁵

Hence remainder when 25 ²⁵ is divided by 9 is the remainder when 7 ²⁵ is divided by 9.

Now 7 ²⁵ = 7 ³ × 7 ³ × 7 ³ .. (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 ²⁵ 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 ²⁵ 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 ₁ and R ₁ be the quotient and the remainder when A is divided by B.

Hence A = B × Q ₁ + R ₁ .

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

k(B × Q ₁ + R ₁ ) = Q × kB + R --> R = kR ₁ .

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 ₁ ).
• The real remainder R is this remainder R1 multiplied by the common factor (k).

Examples

5. What the remainder when 2 ⁹⁶ is divided by 96?

The common factor between 2 ⁹⁶ and 96 is 32 = 2 ⁵ .

Removing 32 from the dividend and the divisor we get the numbers 2 ⁹¹ and 3 respectively.

The remainder when 2 ⁹¹ 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 <>

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

6. Find the remainder when 7 ⁵² is divided by 2402.

Answer: 7 ⁵² = (7 ⁴ ) ¹³ = (2401) ¹³ = (2402 – 1) ¹³ = 2402K + (−1) ¹³ = 2402K −1.

Hence, the remainder when 7 ⁵² is divided by 2402 is equal to −1 or 2402 – 1 = 2401.

Answer: 2401.

2 .1C When dividend is of the form a ⁿ + b ⁿ or a ⁿ – b ⁿ :

EXAMPLES

7. What is the remainder when 3 ⁴⁴⁴ + 4 ³³³ is divided by 5?

Answer:

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

3 ⁴⁴⁴ + 4 ³³³ = (3 ⁴ ) ¹¹¹ + (4 ³ ) ¹¹¹ .

Now (3 ⁴ ) ¹¹¹ + (4 ³ ) ¹¹¹ will be divisible by 3 ⁴ + 4 ³ = 81 + 64 = 145.

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

Hence, the remainder is 0.

8. What is the remainder when (5555) ²²²² + (2222) ⁵⁵⁵⁵ 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) ²²²² + (3) ⁵⁵⁵⁵ is divided by 7.

Now (4) ²²²² + (3) ⁵⁵⁵⁵ = (4 ² ) ¹¹¹¹ + (3 ⁵ ) ¹¹¹¹ = (16) ¹¹¹¹ + (243) ¹¹¹¹ .

Now (16) ¹¹¹¹ + (243) ¹¹¹¹ is divisible by 16 + 243 or it is divisible by 259, which is a multiple of 7.

Hence the remainder when (5555) ²²²² + (2222) ⁵⁵⁵⁵ is divided by 7 is zero.

9. 20 ²⁰⁰⁴ + 16 ²⁰⁰⁴ – 3 ²⁰⁰⁴ − 1 is divisible by:

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

Solution: 20 ²⁰⁰⁴ + 16 ²⁰⁰⁴ – 3 ²⁰⁰⁴ – 1 = (20 ²⁰⁰⁴ – 3 ²⁰⁰⁴ ) + (16 ²⁰⁰⁴ – 1 ²⁰⁰⁴ ).

Now 20 ²⁰⁰⁴ – 3 ²⁰⁰⁴ is divisible by 17 (Theorem 3) and 16 ²⁰⁰⁴ – 1 ²⁰⁰⁴ is divisible by 17 (Theorem 2).

Hence the complete expression is divisible by 17.

20 ²⁰⁰⁴ + 16 ²⁰⁰⁴ – 3 ²⁰⁰⁴ – 1 = (20 ²⁰⁰⁴ – 1 ²⁰⁰⁴ ) + (16 ²⁰⁰⁴ – 3 ²⁰⁰⁴ ).

Now 20 ²⁰⁰⁴ – 1 ²⁰⁰⁴ is divisible by 19 (Theorem 3) and 16 ²⁰⁰⁴ – 3 ²⁰⁰⁴ 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 ² + dx ³ +... is divided by x – a

EXAMPLES

10. What is the remainder when x ³ + 2x ² + 5x + 3 is divided by x + 1?

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

Remainder = (−1) ³ + 2(−1) ² + 5(−1) + 3 = −1

11. If 2x ³ −3x ² + 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

12. What is the remainder when n ⁷ – n is divided by 42?

Answer: Since 7 is prime, n ⁷ – n is divisible by 7.

n ⁷ – n = n(n ⁶ – 1) = n (n + 1)(n – 1)(n ⁴ + n ² + 1)

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

Hence n ⁷ – n is divisible by 6 x 7 = 42.

Hence the remainder is 0.

2.1F Wilson ’s Theorem

EXAMPLE

13. 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

19. 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.

20. 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.

21. 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 ∩ B) – n(B ∩ C) – n(A ∩ C) + n(A ∩ B ∩ 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.