Understanding Remainder based problems for CAT 2012

After an extensive tutorial on graph modification in the second part of a long series on CAT 2012 preparation we look at Remainder theory. .

Here, I will try to cover various concepts related to the questions based on finding the remainders with the help of some examples.

Before moving ahead, let's quickly understand the basic remainder principles first.

When the product of any two or more natural numbers is divided by any natural number then it leaves the same remainder as the product of the individual remainders i.e. if a, b , c and d are integers and k is a positive integer such that,

a = c (mod k)

And, b = d (mod k)

Then, a*b = c*d (mod k)

The same holds true for the other operations as well such as addition, subtraction and division.

i.e. a+b = c+d (mod k)

a-b = c-d (mod k)

(a/b) = (c/d) (mod k)

For example, 75 (= 15*5) which when divided by 4 leaves the remainder of -1 (or 3). And if we consider the product of individual remainders for 15 and 5 with 4, i.e. (-1)*1 which is same when 75 is directly divided by 4.

Euler's Totient Function- usually denoted by Φ(n), gives the number of positive integers less than n, which are co-prime to n.

For any number n (= p^a*q^b*r^c*_____, where p, q, r,____ are prime numbers), Euler's Totient Function is determined as, Φ(n) = n*(1 – 1/p)*(1 – 1/q)*(1 – 1/r)*____

For example, for n = 12 (= 2^2*3), Φ(n) will be 12*(1 – 1/2)*(1 – 1/3) i.e. 4 which means 12 has 4 numbers (1, 5, 7 and 11) less than itself which are co-prime to it.

Euler's Theorem- If two numbers N and K are co-prime to each other,then K^Φ(n) = 1modN

where Φ(n) is the Euler's Totient Function of N.

For example 1), 37^4 when divided by 12, will leave a remainder of 1 as Euler's Totient Function of 12 is 4.

2) In order to find the remainder when 41^97 is divided by 12,

41^97 = 41*41^96

Now as 41^96 = (41^4)^24 = 1mod12 (as 41^4 = 1mod12)

And 41 = 5mod12

=> From the basic remainder principle, 41^97 = (41mod12)*(41^96mod12) = 5*1mod12 = 5mod12.

3) Find the remainder when 12^107 is divided by 37?

Solution- 12^108=12*12^107=1mod37, which means a final remainder of 1 or -36 but as 12 leaves a remainder of 12 when divided by 37, so 12^107 must leave a remainder of -3 (coz -3*12=-36).

Fermat's Theorem- For a prime number P, the Euler's Totient Function will be P(1- 1/P) i.e.equal to (P-1).

So from Euler's theorem, K^(P – 1) = 1modP.

For example 1), 33^12 will leave a remainder of 1 when divided by 13.

2) In order to find the remainder when 43^37 is divided by 13,

43^37 = 43*43^36

Now 43^36 = (33^12)^3 = 1mod13

And 43 = 4mod13.

So, from basic remainder principle, 43^37 = 4*1mod13 = 4mod13.

Wilson's Theorem-

(p – 1)! + 1 is divisible by p if p is a prime number. We can say this also that the remainder when (p-1)! is divided by p, will be -1 or (p-1).

Remember, If p is an integer greater than one then p is prime if and only if (p-1)! = -1 (mod p).

Example- What will be the remainder when 28! is divided by 29?

Solution- As 29 is a prime number. So from Wilson's theorem we can say that 28!+1 will be divisible by 29 or 28! will leave a remainder of -1 (i.e. 28)when divided by 29.

Rem (p-2)!/p = 1, where p is a prime number.

For example Rem(15!)/17 = 1

Remainder Theory for Polynomials- Say, q(x) and r(x) are the quotient and remainder, respectively, when the polynomial f (x) (= a + bx + cx^2 + dx^3 +..) is divided by x − a,

then f (x) = (x − a)q(x) + r(x).

The degree of the remainder will be less than that of the divisor, hence remainder must be constant

So, f (x) = (x − a)q(x) + k.

Substituting x = a in the above equation,

f(a) = k.

Hence, when a polynomial f(x) is divided by (x – a), then the remainder is equal to f (a).

For example 1) When 5x^3 + 7x – 9 is divided by x – 2 will leave a remainder of 5*(2)^3 + 7*2 – 9 i.e. equal to 45.

2) What is the remainder when (81)^21 + (27)^21 + (9)^21 + (3)^21 + 1 is divided by 3^20 + 1?

Solution) Let 3^20 = x

=> We have to find the remainder when f(x) = 81x^4 + 27x^3 + 9x^2 + 3^x + 1 is divided by x + 1.

=> f(-1) = 81 - 27 + 9 - 3 + 1 = 61.

3) What will be the remainder when f(x) = x^71 + x^50 + x^25 + x^9 is divided by x^3 − x ?

Solution) As the degree of the divisor is 3, degree of the remainder will be less than or equal to 2.

=> Say, the remainder is ax^2 + bx + c.

Now, x^71 + x^50 + x^25 + x^9 = q(x)*(x^3 – x) + ax^2 + bx + c = x*(x – 1)*(x + 1)*q(x) + (ax^2 + bx + c).

=> f(0) = 0 = c

f(1) = 4 = a + b + c => a + b = 4

And f(-1) = -1 + 1 -1 -1 = -2 => a – b = -2

=> a = 1 and b = 3

Hence the remainder will be (x^2 + 3x).

With this I will wrap up this post on remainders. For any doubts or queries related to questions based on remainders, feel free to shoot them here.