# Quant Boosters - Anubhav Sehgal, NMIMS Mumbai - Set 4

• Number of Questions - 30
Topic - Number Theory
Solved ? - Yes
Source -

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

• N = 3(5(7k + 6) + 3) + 2 = 105k + 83.
N = 83, 188, 293, 398, 503, etc.
Our required N = 503.
503 mod 35 = 13.

• Q2) If the first 99 natural numbers are written side by side to form a new number 12345678 …. 9899, then how many minimum numbers are to be removed so that, the new number is completely divisible by 11?

• Sum at odd places = 1+3+5+7+9+9(1+2+...+9) = 25+9(45) = 430
Sum at even places = 2+4+6+8+10(1+2+.....+9) = 30+10(45) = 470
Sum => even = 470 and odd => 430
(Sum of digits at odd position from right) - (Sum of digits at even positions from right) = -40
Even - Odd= 40
Remove 99 -> diff =40
Remove 98-> diff =41
Remove 97-> diff =43
Remove 96-> diff =46
Remove 95-> diff =50
Remove 94-> diff =55

We should remove 6 numbers: {99, 98, 97, 96, 95, 94}.

• Q3) N = 4^7 × 5^9 + 2^4 × 7 + 3 × 5^3 + 2^6 × 5^8. How many distinct digits are there in the number N?

• = 32 * 10^9 + 84 + 375 + 25 * 10^6
= 32025000459.
So, 6 distinct digits.

• Q4) S1 = {2, 4, 6, 8, …, 800} S2 = {3, 6, 9, 12, ....., 900} If S3 = S1 ∪ S2, then what will be the 105th element of S3 if all its elements are arranged in increasing order?

• S1 ∪ S2 is a set comprising of all numbers which are multiples of 2 or 3 (or both).
Now, we know that for a number N, there are N(1 - 1/2)(1 - 1/3) = N/3 numbers which are co-prime to 2 and 3 and less than N.

So, there are 2N/3 numbers less than or equal to N which are multiples of 2 or 3 (or both).
=> 2N/3 = 106.
=> N = 159 is 106th such number.
=> 158 should be the 105th number.

• Q5) How many square numbers are in the sequence 11, 111, 1111, . . .?

• A square cannot end with two odd digits. So it simply follows from it that none of these will be square numbers.
Also, 1 and 9 are the only perfect squares having all odd digits.

• Q6) Bill and Clinton take the square of a certain decimal number and express it in base 5 and 6 respectively. Then Bush comes and he takes the two representations and assuming that the expressions are in base 10, adds the numbers. Which digits cannot be the unit digits of the sum?

• Square of number in decimal can have digits : 0,1,4,5,6,9
In Base 5 : 0,1,4
In Base 6 : 0,1,3,4
Sum : 0,1,2,3,4,5,7,8 possible .
6 and 9 not possible.

• Q7) P is the product of first 30 multiples of 30. N is the total number of factors of P. In how many ways N can be written as the product of two natural numbers such that the HCF of these two natural numbers is 19?

• P = 30^30 * 30!
Factorize this.
2^56 * 3^44 * 5^37 * 7^4 * 11^2 * 13^2 * 17 * 19 * 23 * 29
No of factors = 57 * 45 * 38 * 5 * 3 * 3 * 2 * 2 * 2 * 2
19^2 * 2^a * 3^b * 5^c
19x * 19y = Number of factors of product
=> x * y = 2^a * 3^b * 5^c
No of ways = 2^(n-1) = 4 where n = no of distinct primes

• Q8) Find highest power of 1001 in 1001 * 999 * 997 .... 5 * 3 * 1.

• 1001 = 7 * 11 * 13.
The highest power of 1001 in the expression will be the highest power of 13 in the expression.
We will have 13 * 1, 13 * 3, so on up to 13 * (7 * 11) in the above expression as 1001 = 13 * (7 * 11) itself.
=> All odd multiples of 13 up to 13 * (7 * 11)
=> Total multiples = (7 * 11 + 1)/2 = 39 [ Because if 1, 1 * 3, 1 * 5 there => (5 + 1)/2 = 3 multiples there]

Also, we will have additional powers from multiples of 13^2 (=169)

13 * (13 * 1), 13 * (13 * 3), 13 * (13 * 5) will be the multiples of 169 in above expression as 1001 = 13*(77)
so we can have only up till 13 * (65).
This gives us three additional powers of 13 not counted yet.
So a total of 39 + 3 = 42 power of 13 in above expression.
Hence highest power of 1001 in above expression = 42.

Alternate method Multiplying and dividing by the missing numbers, i.e., 2 * 4 * 6 * 8 * ... * 1000, we will get:
1001! / (2 * 4 * 6 * 8 * ... * 1000)
Take 2 common from each term in denominator and it will become 1001! / (500! * 2^500)

=> Exponent of 13 will be = [Exponent of 13 in 1001! - Exponent of 13 in 500!]
=> 77 + 5 – (38 + 2)
=> 42.

• Q9) P is a prime number greater than 30. When P is divided by 30, the remainder is x. How many different values of x are possible?

• P = 30k + x
=> x = P – 30k
Since P is a prime number greater than 30, it will be co-prime to 30.
=> P – 30k will be co-prime to 30 too.
=> x will be co-prime to 30 and less than 30 since 30 is the divisor.
Number of possible values of x = 30(1 – 1/2)(1 - 1/3)(1 – 1/5) = 8.

• Q10) A and B play a game of ‘Dingo’ in which each player in his turn has to choose a positive integer that is less than the previous number but at least half the previous number. The player who chooses 1, loses and the game ends there. A starts by choosing 2021 and after that both the players (A & B) continue to play with the best strategy. Which integer should B choose immediately after A has chosen 2021, to ensure his own victory?

63

34

47

61

63

61

58

65