goyalsau wrote:if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15.
This is a high level remainder problem.
The solution Shovan provided is not correct. Check the number. It satisfies the 13 criteria only. The following solution contains some critical logical reasoning. Read carefully. If there is any problem, let me know.
The number should be written in the following ways,
- 1. n = 11a + 6
2. n = 13b + 4
3. n = 15c + 9
Where a, b, and c are non-negative integers.
Our job is to combine all these three to get a single expression for n, from which we can easily determine the smallest possible value.
Combining first two relation we can say (13b + 4) gives a remainder of 6 when divided by 11. Now, (13b + 4) = 11b + (2b + 4). Hence (2b + 4) also gives a remainder of 6 when divided by 11. Which again implies 2b will give a remainder of (6 - 4) = 2 when divided by 11. Hence b will give a remainder of 1 when divided by 11. Thus, b can be written as (11x + 1) for some non-negative integer x.
Hence, n = 13*(11x + 1) + 4 = (143x + 17)
Now we have to combine this with the third relation. Which clearly implies (143x + 17) will give a remainder of 9 when divided by 15. Now, (143x + 17) = (135x + 8x + 15 + 2) = 15*(9x + 1) + (8x + 2). Hence (8x + 2) also gives a remainder of 9 when divided by 15. Which again implies 8x will give a remainder of (9 - 2) = 7 when divided by 15. Thus, 8x must be of the form (15y + 7) for some non-negative integer y. Note that this means 8 divides (15y + 7) = (8y + 7y + 7) = 8y + 7(y + 1). Again this implies 8 divides 7(y + 1). Now as 8 doesn't divide 7, 8 must divide (y + 1). Thus y) must be of the form (8z + 7) for some non-negative integer z. Hence, 8x = (15y + 7) = 15*(8z + 7) + 7 = (120z + 112) = 8*(15z + 14). hence x is of the form (15z + 14) for some non-negative integer z.
Hence, n = 13*(11x + 1) + 4 = (143x + 17) = 143*(15z + 14) + 17 = (2145z + 2019)
Hence minimum possible value of n is 2019.
Note: I believe the original question belongs to CAT and it looks something like "
Find the sum of the remainders obtained when a number n is divided by 9 and 7 successively, if n is the smallest number that leaves respective remainders of 4, 6 and 9 when divided successively by 13, 11 and 15."
Am I right Saurabh?
