Quant Boosters  Anubhav Sehgal, NMIMS Mumbai  Set 3

Number of Questions  30
Topic  Number Theory
Solved ?  Yes
Source 

Q1) How many different marks are possible in CAT if there are 100 questions with marking scheme of +3 , 1 & 0 for correct, wrong & non attempt resp

If no of marks are +n for correct and 1 for incorrect, then number of scores which are not possible is given by :
(n  1) + (n  2) + .. + 1 = n(n  1)/2
Take +4 1 scheme
30 correct gives : 120
29 correct gives : 116
With 30 correct you can have 0 wrong
So 1,2,3 wrong are not possible with 30 correct
With 29 correct you can have 1 wrong
But 2,3 Qs wrong is not..
..
(n  1) + (n  2) + .. + 1 = n(n  1)/2
Which is nothing but C(n,2)

Q2) How many positive integer solution for the equation x1 + x2 + x3 + … + xk = n, where 1 < = x1 < = x2 < = x3 … < = xk?

a + b + c = 10
1 < = a < = b < = c
a = p + 1
b = p + q + 1
c = p + q + r + 1
where p,q,r are non negative integers.
3p + 2q + r = 7
p = 0, 2q + r = 7 => 4 solutions
p = 1, 2q + r = 4 => 3 solutions
p = 2, 2q + r = 1 => 1 solution
Total : 8 solutions

Q3) Find the sum of all positive integral value a for which (2a + 124)/(a + 3) is an integer.

2a + 124)/(a + 3)
2(a + 62)/(a + 3)
2[(a + 3 + 59)]/(a + 3)
2 + 118/(a +3)
a + 3 is a factor of 118
118 = 2 * 59
1,2,59,118
a = 2,1,56,115
Sum of positive integral values = 171

Q4) Find (7^21 + 7^22 + 7^23 + 7^24) mod 25.

7^21(1 + 7 + 49 + 343) mod 25
(7^21 * 400) mod 25
0 since 400 is divisible by 25.
[N = N1 * N2 *…, then N mod x = N1 mod x * N2 mod x * … i.e. Remainders are multiplicative]

Q5) Find 17! mod 23.

We know that (p – 2)! Mod p = 1 for any prime p.
21! Mod 23 =1
21 * 20 * 19 * 18 * 17! Mod 23 = 1
(2) * (3) * (4) * (5) * 17! Mod 23 = 1
[21 mod 23 = 21 or 2; In general, k mod n = k or (k – n) when k < n]
120 * 17! Mod 23 = 1
5r mod 23 = 1
r = 14 as 70 mod 23 = 1.

Q6) If f (x) = x^3 + x^2 + 2x – 1 is divided by (x + 2) gives remainder r and quotient q (x). Then, find the value of q (2) + r.

Q7) Find remainder when 987987987… (123 digits) is divided by 1001.

1001 = 10^3 + 1
So, we may for triplets from right to left and take alternative signs + and –ve moving from right to left.
123 digits means 41 triplets of three digits 987 each.
When we take alternating sums from right to left, we will get,
[(987 – 987) + (987 – 987) + … 20 such brackets] + 987 mod 1001 = 987.

Q8) Find the remainder when 3^45 is divided by 125.

The usual and the longer approach
3^5 = 243. 243 mod 125 = 118 or 7
3^45 mod 125 = (7)^9 mod 125
Now, 7^4 mod 125 = 2401 mod 125 = 26 [ You basically try to break it into powers which leave a smaller remainder with our divisor to make our calculations manageable. That’s why we didn’t take 7^2 =49, 7^3 = 343.]
(7)^4 * (7)^4 * (7) mod 125
= 26 * 26 * 7 mod 125
= 676 * 7 mod 125
= 51 * 7 mod 125
= 357 mod 125
= 18 or 107.Smart approach [Will come from practice only]
Your first instinct here could have been to use Euler. But when you notice E(125) = 100 and you are not getting near that power with multiples of 45, you decided to drop the idea. Some reverse engineering is being done here so note carefully the approach.
3^45 mod 125 is to be found
128 mod 125 = 3.
So can we write 3^45 mod 125 = 128^45 mod 125? Sure we can but who thinks of going the other way round.
What this does for us?
128 = 2^7 thankfully and we get,
3^45 mod 125
= (2^7)^45 mod 125
= 2^315 mod 125
= 2^15 mod 125
= 2^7 * 2^7 * 2 mod 125
= 3 * 3 * 2 = 18.
That simple by just going the other way round. A little out of the box thinking

Remainder when f (x) is divided by (x – a) = f (a).
r = f (2) = 8 + 4 – 4 – 1 = 9
q (x) = x^2 – x + 4 => q (2) = 4 – 2 + 4 = 6
q (2) + r = 3

Q9) Find the remainder when 2^2014 + 7 * 5^4020 is divided by 23

E(23) = 22
2014 mod 22 = 12
4020 mod 22 = 16
2^12 + 7 * 5^16 mod 23
64 * 64 + 7 * 25^8 mod 23
5 * 5 + 7 * 2^8 mod 23
25 + 7 * 256 mod 23
= 25 + 21 mod 23
= 0

Q10) Find the remainder when 77777 … 70 times is divided by 37