Best of CAT (Common Admission Test) - 2

This post is the second in the series of my efforts to solve some of the best CAT problems in both theory and programming. It gives me a great pleasure to solve and then verify the answers to some puzzles using C++ or Python and sometimes SAS.

Here is an interesting puzzle that will make you look like a geek (or a nerd - depends on how you look at Mathematics) when you pose it to a group.

Question: There is a certain number X which when divided by Y, where all Y ε [1,10] yields a remainder (Y-1). That is, when X is divided by Y, which takes all values from 1 through 10, the remainder is (Y-1). To be more clear, if X is divided by 10 then the remainder is 9, if X is divided by 9 then the remainder is 8, so on and so forth, if X is divided by 3 then the remainder is 2. The condition should hold good for all numbers from 1 to 10. What is the least number X can take to satisfy this condition? (Hint: X is less than 3000.)

Solution: I programmed this in C++ and it is pretty straight-forward.

The same thing can be implemented in SAS. Let me withhold the answer for now.

Coming to the more important part - to solve this problem by implemting theoritical concepts. This problem pertains to Number Theory. 'Least Common Multiple' doesn't need any introduction. When there are a set of divisors that yield the same remainder (Remainder = 1 in this case), the least number that satisfies this condition =

LCM of those divisors - Common remainder.

By solving, the LCM of numbers 1 through 10 is 2520. Hence the answer = 2520 - 1 = 2519.

All multiples of LCM have the same property. (5040 - 1), (7560 - 1) etc, all have the same property. The objective here is to obtain the least number which satisfies the condition which is 2519. More often than not, confusion prevails in CAT. Also, time is premium in these tests and so the standard method of obtaining LCM may not work well if the divisors are too many or too big. Taking cues from the answers and back solving will be lot helpful. In this problem, it is stated that division by 10 yields 9 which implies that the last digit is 9. That holds the key to solve this problem.