Quant Boosters  Anubhav Sehgal, NMIMS Mumbai  Set 1

Number of Questions  30
Topic  Number Theory
Solved ?  Yes
Source 

Q1) Two numbers when divided by m (m < = 7) gives remainder 3 and 4. The remainder when the sum of these two numbers is divided by the same divisor is R. Find the value of R + m.

Let the two numbers be a and b
a = mq + r1
b = nq + r2
Then, (a + b) = (m + n)q + (r1 + r2)
Remainder when sum of two numbers (giving individual remainders r1 and r2 with a divisor) is divided by the same divisor is :
R = (r1 + r2)  divisor [if this is positive]
else
R = (r1 + r2)
Here R = (3 + 4)  m
R + m = 7

Q2) Calculate GCD(1,155) + GCD(2,155) + .. + GCD(155,155). where GCD(m,n) is the greatest common divisor of m and n.

GCD(x,155) = 1 unless x is a multiple of 5 and/or 31
4 onlymultiples of 31
30 onlymultiples of 5
1 multiple of both 31 and 5
35 such numbers
Hence,
Sum = 4 * 31 + 30 * 5 + 1 * 155 + (155  35) * 1 = 549This is an example of how test setters combine two simple concepts to trap you.

Q3) Find the largest number n such that (n  11) divides n^3 + 83.

A mix of elementary algebra and number system
By remainder theorem,
Remainder when n^3 + 83 is divided by (n  11) = 11^3 + 83 = 1414
Now,
(n  11) * k = 1414
For largest n,
k = 1, (n  11) = 1414
n = 1425

Q4) Consider natural numbers a, b, c, d and e.Three statements are provided:
I. (de)^2 = abbb
II. (ee)^2 = ccbb
III. A perfect square never ends with c,d and e.Which of the following statements are sufficient to determine the arithmetic mean of a, b and c?
a) Any of the three statements
b) Any two of the three statements
c) Statement I and II are sufficient
d) Statement II and III are sufficient
e) All three statements are necessary

Square with largest occurrence of a nonzero digit at the end is 38^2 = 1444
The only square of the form XX^2 = YYZZ is 88^2 = 7744
A square never ends with 2,3,7,8 or odd number of zeroes
Combine them, analyze the options and you ll find I and II are sufficient to answer what we need which is primarily values of a,b,c.

Q5) Find 24^1202 mod 1446.

1446 = 2 * 3 * 241
When we cancel out some common term from dividend and divisor, we need to multiply it back in the end.
24^1202 = (2^3 * 3)^1202 = 2^3606 * 3^1202
2^3605 * 3^1202 mod 3*241Use Chinese remainder theorem now,
N = 2^3605 * 3^1202 N mod 3 = 0
E(241) = 240
N mod 241 = 2^3605 * 3^1202 mod 241 = (2^5 * (2^240)^15) * (3^2 * (3^240)^5) mod 241
[Taking out powers in multiple of Euler number, as they would leave remainder as 1 with 241.]
N mod 241 = 2^5 * 3^2 mod 241 = 47
3a = 241b + 47
a = (240b + 45)/3 + (b + 2)/3
a = 80b + 15 + (b + 2)/3
b = 1, a = 96
Remainder = 288
Final remainder = 288*2 = 576 [ Remember we needed to multiply the 2 canceled out earlier back]Alternate approach
We know that for a prime p, N^(p – 1) mod p = 1 ; By extension of Euler theorem which is also called Fermat’s remainder theorem. That is to say, Cyclicity of obtaining remainder 1 is E (p).
Extending that logic, 1446 = 2 * 3 * 241
Cyclicity of 1446 = LCM (E (2), E (3), E (241)) = LCM (1, 2, 240) = 240
24^1202 mod 1446 = (24^240)^5 * 24^2 mod 1446 = 1 * 576 mod 1446 = 576

Q6) The product of 3 numbers a, b and c is 12 times their HCF. Find the number of ordered triplets (a,b,c) satisfying this condition?

Numbers : hp,hq,hr where h is the hcf
h^3. pqr = 12h
h^2. pqr = 12
h = 1 => pqr = 12 => 18 ordered sets
h = 2 => pqr = 3 => 3 ordered sets
Total : 21 ordered sets

Q7) Find the highest N such that 11^N divides (97! + 98! + 99!)

OA : 10, Guess doesn't need any discussion here :)

Q8) When a number N(N > 500) is successively divided by 3,5,7, it leaves a remainder of 2,3,6 respectively. Find the remainder when 2nd such smallest N is divided by 35.

N = 3(5(7m + 6) + 3) + 2 = 105m + 101
N = 101,206,311,416,521,626
626 mod 35 = 31

Q9) Find the highest power of 1001 in 1001 * 999 * 997 * 995 * ... * 3 * 1

Approach 1 :
Multiply and divide by 2 * 4 * 6 * 8 *... * 998 * 1000
Number = 1001!/(2 * 4 * 6 * 8 * .. * 998 * 1000) = 1001!/2^500 * 500!
Exponent of 13 in this = (77 + 5)  (38 + 2) = 42Approach 2 :
For power of 13, 13 * 1 to 13 * (7 * 11) all odd powers
So, (7 * 11 + 1)/2 = 39
For 13^2,
13 * (13 * 1), 13 * (13 * 3), ... upto 13 * (13 * 5)
So additional three powers.
Total = 39 + 3 = 42

Q10) If p, q, and r are positive integers such that (p + q  r)(q + r  p)(p + r  q) = 15, then what is the product of p, q and r?
a) 24
b) 60
c) 64
d) Cannot Be Determined