# [easy]Remainder

Arjun Shastry
Ranch Hand
Posts: 1899
1
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
Rancher
Posts: 13459
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
Ranch Hand
Posts: 4632
The answer is probably a simple formula, but here's a bit of a brute force way (needs error handling)

David O'Meara
Rancher
Posts: 13459
I'm sure there's something I'm missing.
I almost see a pattern but I'm not quite there.

David O'Meara
Rancher
Posts: 13459
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.