CAT Remainders Questions with Solutions

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. Therefore, remainder = 4

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. Therefore, remainder = 1

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. Therefore, remainder = 4

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.

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.

Remainder = 64

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.

Remainder = 2401.

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.

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.

We can arrange the term as:

\({20^{2004}} + {16^{2004}} - {3^{2004}} - 1 = \left( {{{20}^{2004}} - {3^{2004}}} \right) + \left( {{{16}^{2004}} - {1^{2004}}} \right).\)

We know that \({a^n} - {b^n}\) is divisible by (a+b) and (a-b) when n is odd.

Therefore, \({20^{2004}} - {3^{2004}}\) is divisible by 17 and \({16^{2004}} - {1^{2004}}\) is divisible by 17

Hence the complete expression is divisible by 17 .

Similarly, \({20^{2004}} + {16^{2004}} - {3^{2004}} - 1 = \left( {{{20}^{2004}} - {1^{2004}}} \right) + \left( {{{16}^{2004}} - {3^{2004}}} \right).\)

Now \({20^{2004}} - {1^{2004}}\) is divisible by 19 and \({16^{2004}} - {3^{2004}}\) is divisible by 19 .

 Hence the complete expression is also divisible by 19 .

Hence the complete expression is divisible by \(17 \times 19 = 323\).

5 and 63 are coprime to each other, therefore we can apply Euler’s theorem here.

63 = 3² × 7 $\Rightarrow$ $\phi (63)=63(1-\frac{1}{3})(1-\frac{1}{7})=36$

Therefore, Remainder $[\frac{{{5}^{37}}}{63}]$

=Remainder $[\frac{{{5}^{36}}\times 5}{63}]=5$

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.

31 is a prime number therefore f(N) = 30. 52 and 31 are prime to each other. Therefore, by Fermat’s theorem:

Remainder $[\frac{{{52}^{30}}}{31}]=1$

$\Rightarrow$ Remainder $[\frac{{{52}^{60}}}{31}]=1$

By Wilson’s theorem, we can see that 40! + 1 is divisible by 41

$\Rightarrow$ Remainder$[\frac{40!}{41}]=41-1=40$

In the above problem, we saw that the remainder when 40! is divided by 41 is 40.

$\Rightarrow$ 40! = 41k + 40 $\Rightarrow$ 40 × 39! = 41k + 40. The R.H.S. gives remainder 40 with 41 therefore L.H.S. should also give remainder 40 with 41. L.H.S. = 40 × 39! where 40 gives remainder 40 with 41. Therefore, 39! should give remainder 1 with 41.

By Fermat’s Little Theorem 10⁶ will give remainder as 1 with 7.

Remainder $\left[ \frac { 10 ^ { 10 } } { 7 } \right] =$ Remainder $\left[ \frac { 10 ^ { 6 } \times 10 ^ { 4 } } { 7 } \right]$

=Remainder $\left[ \frac { 10 ^ { 4 } } { 7 } \right] =$ Remainder $\left[ \frac { 3 ^ { 4 } } { 7 } \right] = 4$

Similarly, all the other terms give remainder of 4 with 7. Therefore, total remainder = 4 + 4 + 4… (10 times) = 40.

Remainder of 40 with 7 = 5

Note that here 8 and 132 are not co-prime as HCF (8, 132) = 4 and not 1. Therefore, we cannot apply Euler’s theorem directly.

Remainder $\frac { 8 ^ { 643 } } { 132 } ] =$ Remainder $\left[ \frac { 2 ^ { 1929 } } { 132 } \right] = 4 \times$ Remainder $\left[ \frac { 2 ^ { 1927 } } { 33 } \right]$

Now we can apply Euler’s theorem.

$\phi ( 33 ) = 33 \left( 1 - \frac { 1 } { 3 } \right) \left( 1 - \frac { 1 } { 11 } \right) = 20$

$\Rightarrow$ Remainder $\left[ \frac { 2 ^ { 20 } } { 33 } \right] = 1$

= Remainder $\left[ \frac { 2 ^ { 1927 } } { 33 } \right] =$ Remainder $\left[ \frac { 2 ^ { 7 } } { 33 } \right] = 29$

$\Rightarrow$ Real remainder $= 4 \times 29 = 116$