gmatusa2010 wrote:Rahul,
That's exactly what I did. Just wondering if there's another way. (I think this is the fastest). Or to put it another way, just to extract more learning out of this experience. Is there anyway to combine the 5a+1 and 7b+3 to create something that will yield n=35q+ something? More theoretically/abstract approach.
There is a famous theorem related to these kind of problems; Chinese Remainder Theorem. A details discussion is available here:
https://www.cut-the-knot.org/blue/chinese.shtml
I am not going into the detail of the theorem. Understanding of the theorem needs a clear knowledge of Modulo (Remainder) Arithmetic. I believe application of CRT in problems like these will consume more time unless the problem is too complicated or you are super-fluent with CRT.
In general, application of CRT in these kind of problems can be summarized as follows,
- If a positive integer n when divided by a, the remainder is p and when divided by b, the remainder is q, then n is of the form [LCM(a, b)*t + s]. Where t = 0, 1, 2.. and s is the lowest such n.
For example for this problem, s = minimum such n, i.e. 31. Thus n is of the form [LCM(5, 7)*t + s] = (35t + 31), where t is any non-negative integer.
Now you may ask that for finding s we have to go for the old list method we were using, then what is the profit of using CRT? Well, if you apply CRT properly you'll automatically get the value of s, you don't have to look for it. But if you apply this summarized version of CRT, you have to find the value of s manually.
