[easy]Remainder

[Arjun Shastry]

This puzzle appeared two weeks back in newspaper.I couldn't find the answer.See if you can solve.
Choose any number between 1 to 100(including 1 and 100).Get the remainders when it is divided by 3,5,7.So if I choose 37,I get 1,2,2.Problem is you will be given the remainders and you have to find the simplest way to find the number from those remainders.
[We can do using simple iterations(for eg. 1,3,4.I will start with 11 then 18 i.e.multiples of 7 and doing that) but they want much simpler way]
Any idea?

[David O'Meara]

Hmm, simultaneous equations?
3x + 1 = m (1)
5y + s = m (2)
7z + 2 = m (3)
(2-1) 5y - 3x + 1 = 0 (4)
(3-1) 7z - 3x + 1 = 0 (5)
(5-4) 7z - 5y = 0
Gives us the ratio 7/5, choose z=5 (and therefore y=7)
(into 3) 7*5 + 2 = 37
This is only that neat due to the remainders from the initial question.
It wouldn't happen so neatly otherwise.
An easier solution than this?

[Michael Dunn]

The answer is probably a simple formula, but here's a bit of a brute force way (needs error handling)

class Remainder
{
  public static void main(String args[])
  {
    int combos[] = new int[247];
    for(int i = 1; i < 101; i++) combos[Integer.parseInt(""+i%3+i%5+i%7)] = i;
    System.out.println(combos[Integer.parseInt(args[0]+args[1]+args[2])]);
    System.exit(0);
  }
}

[David O'Meara]

I'm sure there's something I'm missing.
I almost see a pattern but I'm not quite there.

[David O'Meara]

Here's where I'm up to. Maybe someone else can finalise a solution...
3x + a = m
5y + b = m
7z + c = m
Therefore:
3x + a = 5y + b
3x + a = 7z + c
5y + b = 7z + c
You can always modify these equation to the form:
3(x + a') = 5(y + b')
(It is trivial when a=b, b=c or a=c)
eg:
remainder 1, 0, 3
3x + 1 = 7z + 3 (subtract 3 from either side)
3x + 1 - 3 = 7z (gobble the 3)
3(x-1) + 1 = 7z (subtract 6 from both sides)
3(x-1) - 6 + 1 = 7z - 6 (gobble the 6)
3(x-3) + 1 = 7z - 6 (subtract 1 from both sides)
3(x-3) = 7z - 7
3(x-3) = 7(z-1)
One solution is 0=0, x=3, z=1, substitution gives y=2 which agrees with our 0=0 assumption
Therefore m=10 QED (only cos we don't have to look to the next solution)
If we had to go to the next solution:
21=21, x=10, z=4 gives m=31, but the 'y' remainder is 1, not 0
etc.