Question

Can you divide 1000 into two parts such that one part is a multiple of 47 and the other a multiple of 19?

Answer 1

Answer:

1000 = 658 + 342 = (14)(47) + (18)(19)

Step-by-step explanation:

Using Euclid's Algorithm:

47 = 2 × 19 + 9

19 = 2 × 9 + 1

Then reverse:

1 =  19 - 2 × 9

 =  19 - 2 × ( 47 - 2 × 19 )

 =  19 - 2 × 47 + 4 × 19

 =  5 × 19  -  2 × 47

Multiply by 1000 to get:

1000 = 5000 × 19  -  2000 × 47

We don't want a "minus" in there, so now we modify the 5000 and 2000 without changing the sum:

1000 = ( 5000 - 47k ) × 19  -  ( 2000 - 19k ) × 47

        = ( 5000 - 47k ) × 19  +  ( 19k - 2000 ) × 47

We want (5000-47k) and (19k-2000) to both be positive.

To avoid making (5000-47k) negative, we want to keep k small.  So we choose k as small as possible to make 19k - 2000 positive.

2000 / 19 = 105.....,   which means 19 × 105 is just below 2000.

So take k = 106.

• 5000 - 47 × 106 = 18
• 19 × 106 - 2000 = 14

This gives the requires result:

1000 = 18 × 19  +  14 × 47