2IIM Quant Notes  Number Theory  Part 1

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
N is an 80digit positive integer (in the decimal scale). All digits except the 44th digit (from the left) are 2. If N is divisible by 13, find the 44th digit.
Hint: 1001 is 7 * 11 * 13. 1001 is a fabulous number. Kind of number you want to make your friend. A number that will take all your inputs replicate them and appreciate your efforts amply.
Another hint: A number of the form abcabc is a multiple of 1001 and therefore a multiple of 13. So, 222222 is a multiple of 13. 222222 followed by any number of zeroes is also a multiple of 13.
22222....222 thirtysix times is a multiple of 13... 2222.....22 fortytwo times is also a multiple of 13.
Answer is 6
A page is torn from a novel. The sum of the remaining page numbers is 10000. What is the sum of the two pagenumbers on the torn page of this novel?
Hint: Do not just think algebra. Think 'around' 10000.
Sum of natural numbers is n(n+1)/2
To get close to 10000, we need n to be 141. 141*142/2 is equal to 10011, which means we are short 11. Two consecutive numbers must add to 11, the only possibility is 5+6
A number n! is written in base 6 and base 8 notation. Its base 6 representation ends with 10 zeroes. Its base 8 representation ends with 7 zeroes. Find the smallest n that satisfies these conditions ?
Hint : In base 5, if a number ends in 4 zeroes, it should be a multiple of 5^4.
From this we can Say the number should be a multiple of 2^21 and also 3^10. Since we know in base six, the number ends in 10 zeroes, the power of three is the limiting factor.
So we need a number that is a multiple of exactly 3^10 and a multiple of at least 2^21 (we can go up to 2^23, but not 24. Think about why this is)
Trial and error works best here. If n is 18, then through repeated division, we get 18! Is a multiple of 3 power 8. We need two more multiples of 3, so let's check 24!
This is a multiple of 3 power 10. It is also a multiple of 2 power 22, so it fits the constraints. 24 is the smallest such number. 25 and 26 will also work since they don't bring in extra multiples of three
[x] is the greatest integer less than or equal to x. Find the number of positive integers n such that [n/11] = [n/13].
The greatest integer function is a fabulous discrete function. Any question on this, treat with caution.
All numbers less than 11 will yield 0 as a result for both 11 and 13. Straight away we have 10 numbers.
Next 11 and 12 will yield 1 in the first case and 0 in the Second, so ditch these. We need to look for the range where n is less than 22.
From 13 to 21, both cases will yield 1 as the answer. Add another 9 cases. Next overlap is from 26 to 32, for another 7 cases
Next overlap is from 39 to 43, for 5 more cases. Next overlap is from 52 to 54 for 3 more cases. The final case is 65 when the result is five in both cases.
Total number is 35
N/420 is a terminating decimal. If N is a natural number less than 420, how many different values can N take ?
Hint/Method: Any number of the form p/q is a terminating decimal if and only if the the only primes that divide q are 2 and 5. The caveat here is that p/q should be in its simplest form. In other words HCF(p,q) = 1. p, q should be coprime
A man wants to leave his wealth for his 5 sons and/or 11 grandchildren. He realizes that if he distributes his wealth equally amongst his sons, he has $2 left. If he distributes it equally amongst his grand kids, he has$3 left. If he distributes it equally among all his progeny, he has $4 left. What is the least amount of money the old man might be leaving behind?
In the first case, we get that his wealth is in the form 5a + 2, in the second, 11b + 3, and in the final, 16c + 4. Let's list down some numbers....
In the first case,
.... 22, 27, 32, 37, 42, 47, 52....
In the second case,
... 14, 25, 36, 47, 58...We see the number has to be of the form 55k + 47
Listing,
47, 102, 157, 212, 267, 322...
In the third case
..., 100, 116, 132... 164, ... 196, 212So his wealth should be of the form 880k + 212. Obviously the smallest is when k is zero, or 212 is the minimum possible.
Number N = 333333……3 written 2016 times. What is the remainder when N is divided by 55 ?
N/11 remainder is 0. N/5 remainder is 3. Combine these two and we get 33.
Number N = 333333……3 written 2016 times. What is the remainder when N is divided by 56 ?
The number is of the form 8k + 5 ( remainder when divided by 8 is 5, just look at last three digits)
Also, 333333 is exactly divisible by 7, I found this painstakingly.... Even though just two questions back we saw abcabc is divisible by 1001...
This means repeated sets of 333333 will also be divisible by 7. Since 2016 is 6 * 336, the number is exactly divisible by 7.
So we have a number of the form 8a + 5, and 7b
Listing, we have
5, 13, 21....
21 is a multiple of 7. So the number is of the form 56k + 21.
Remainder when divided by 56 is 21How many 5 digit numbers exist, comprising the digits 1, 2, 3, 4, 5 each occurring exactly once that such that ‘1’ does not appear immediately before ‘2’, but are divisible by 12. (Ex. 34152 would be counted, whereas 34512 would not be counted)
For a number to be divisible by 12, it needs to be divisible by 3 and 4. Three is not a problem because in any configuration, the sum of digits will be 15, so the number is divisible by 3.
To be divisible by 4, the last two digits must be a multiple of 4. There are four ways this is possible, the no ends with 12, 24, 32 or 52. We can't consider 12 because one immediately precedes 2.
So there are three cases we need to consider. Let us consider 32 and 52, since there is no scope for 1 to appear before 2 in these cases.
The number looks like _ _ _ 3 2/ 5 2. In both cases, the other three digits can rearrange in 3! Ways. So six cases each for these two cases.
In the last case, there are six arrangements possible. But let us consider the arrangements which end in _ _ 1 2 4. There are 2! Cases which must be eliminated, for a total of four more cases.
All cases considered, there are 16 such numbers