# [easy]Remainder

Arjun Shastry

Ranch Hand

Posts: 1898

1

posted 12 years ago

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?

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?

MH

posted 12 years ago

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?

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

posted 12 years ago

I'm sure there's something I'm missing.

I almost see a pattern but I'm not quite there.

I almost see a pattern but I'm not quite there.

posted 12 years ago

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.

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.

It is sorta covered in the JavaRanch Style Guide. |