Quant Boosters  Anubhav Sehgal, NMIMS Mumbai  Set 2

123234345456567678789 mod 37
10^3 mod 37 = 1
Hence we can form groups of 3 digits from right,
Find individual remainders, and
Add them up for final remainder.
123 mod 37 = 12
234 mod 37 = 12
..
789 mod 37 = 12
7 * 12 mod 37 = 10 = Answer

Q18) Find 10111213141516171819 mod 33

10111213141516171819 mod 33
10^2 mod 33 = 1
Hence we can form groups of 2 digits from right,
Find individual remainders, and
Add them up for final remainder
(10 + 11 + 12 + .. + 19) mod 33
145 mod 33 = 13

Q19) Find (13^3 + 14^3 + ... + 34^3) mod 35

(13^3 + 14^3 + ... + 34^3) mod 35
[34 * 35/2]^2  [12 * 13/2]^2 mod 35
[35*17]^2  [78]^2 mod 35
(0  64) mod 35
29 or 6

Q20) When a natural number M is divided by 4 and 7, it gives remainder 3 and 2 respectively. Even when another natural number N is divided by 4 and 7, it also gives remainder 3 and 2 respectively. There is no other number in between M and N exhibiting these properties. P is a natural number that gives the same remainder after dividing each of M and N. How many values of P are possible?

4a + 3 = 7b + 2
a = 5, b = 3
Number = 23 + 28k
Let M = 23 + 28a
and N = 23 + 28b
Since P leaves same remainder with each M and N
Therefore P must be a factor of 28 since constant(23) will leave same remainder.
Final remainder will depend on 28k term which can be same for both M and N
if it is a factor of 28.
1,2,4,7,14,28 : 6 Values

Q21) Find 24^1202 mod 1446

24^1202 mod 1446
1446 = 2 * 3 * 41
Cyclicity of 1446 = LCM(1,2,240) = 240
24^1202 mod 1446
(24^240)^5 * 24^2 mod 1446
1 * 576 mod 1446
576

Q22) Find the remainder when [102010!/(51005!^2) is divided by 101

[102010!/(51005!^2) mod 101
Direct application of Lucas Theorem
Primarily used for finding remainders of large binomial coff with some prime p
Here,
[102010!/(51005!^2) = C(102010,51005)
Since, 102010 = 10(101)^2 + 0(101) + 0
or A00 in base 101 representation
and
51005 = 5(101)^2 + 0(101) + 0
or 500 in base 101 representation
C(102010,51005) mod 101
= C(10,5) * C(0,0) * C(0,0)
= 50 * 1 * 1 = 50

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

Approach 1 :
(7^21 + 7^22 + 7^23 + 7^24) mod 25
7^21(1 + 7 + 49 + 343) mod 25
7^21 * 400 mod 25 = 0Approach 2 :
E(25) = 20
So,
(7^21 + 7^22 + 7^23 + 7^24) mod 25
(7 + 49 + 343 + 2401) mod 25
7  1  7 + 1 = 0

Q24) Let X be the largest positive number less than 10^6 such that when written in base 2, the binary representation consists of only 1s. Find the remainder when (X+2) is divided by 3.

2^10 = 1024 > 10^3
(2^10)^2 > 10^6
=> 2^19 is the largest power of 2 less than 10^6
For a binary representation with all 1s, X must be
2^19  1
So (X + 2) mod 3 = (2^19 + 1) mod 3 = 0

Q25) Find the LARGEST 5digitinteger N so that 2N is also a 5digitinteger and all digits 0, 1, 2, 3, ..., 9 are contained in both N and 2N

Idea is that we have to maximize the digits.
4 has to be first digit of N. Giving us 9 as first digit of 2N ( 2 * 4 + 1 carryover)
Second digit of N cannot be 9, Since 9 is already first digit in 2N.
So let 8 be second digit of N. We have 2 * 8 = 16 +1 carryover = 17 giving 7 as the second digit of 2N.
Now let 6 be the 3rd digit of N. we have 2 * 6 = 12 + 1 carryover = 13 giving us 3 as the 3rd digit of 2N.
Now let 5 be the 4th digit of N. We have 2 * 5 = 10 giving us 0 as the 4th digit of 2N.
Finally we have 1 as the fifth digit of N giving us 2 as the last digit of 2N.
So the required numbers are : 48651 and 97302.

Q26) Smallest whole number which when divided by 5,7,9 and 11 leaves the remainder 1,2,3 and 4 respectively.

Note here that 5 – 1 is not equal to 7 – 2 is not equal to 9 – 3 is not equal to 11 – 4.
So you cannot apply LCM (5, 7, 9, 11) – N where N is the constant difference.
N = 5a + 1
N = 7b + 2
N = 9c + 3
N = 11d + 4Multiply each by 2 so that remainders also count by a gap of 2 like the divisors are doing.
2N = 5(2a) + 2
2N = 7(2b) + 4
2N = 9(2c) + 6
2N = 11(2d) + 8Now divisors and remainders share a common difference of 3. Designating them as new variables
M = 5l + 2 = 7m + 4 = 9n + 6 = 11o + 8
Least M = LCM (5, 7, 9, 11) – 3
Least N = [LCM (5, 7, 9, 11) – 3]/2 = 1731 since M = 2N.Seeing the procedure you can now directly solve such questions in one line.
Take LCM of divisors. Subtract the would be common remainder after you have figured out the number to multiply with to make the count of divisors and remainders of the same step.
[Here Count of divisors was of 2 : 5, 7, 9, 11 and remainders was of 1. So we multiplied by 2/1 = 2]Another example : Divisors are 5,8,11 ; Remainders are 3,5,7. Multiplier = 3/2. See common remainder and then, Answer : [LCM(5,8,11) – 0.5]/(3/2) = 440 – 0.5/ (1.5) = 439.5/1.5 = 879/3 = 293
NOTE : General form of number will be = Smallest number + k * LCM(Divisors). You may be asked to find the kth smallest number or some other variant. So you may add multiples of LCM to the smallest number to get the required answer.

Q27) A positive integer p is called almost prime, when it has only 1 divisor aside from 1 and p. Find the sum of the 6 smallest almost primes.