Originally Posted by

**Opalg** This is an exercise in using Euclid's algorithm. (If you haven't come across this, Google it to see why the following calculations are being done.)

$\displaystyle \begin{aligned}55&=42+13\\ 42&= 3(13) + 3\\ 13&= 4(3) + 1.\end{aligned}$

Now work through those equations in the reverse order to get

$\displaystyle \begin{aligned}1&= 13-4(3)\\ &= 13 - 4(42-3(13)) = -4(42) + 13(13)\\ &= -4(42) + 13(55-42) = -17(42) + 13(55).\end{aligned}$

So one solution to the equation 42x+55y=1 is x=–17, y= 13. You get the other solutions by adding a multiple of 55 to x, and subtracting the same multiple of 42 from y. Thus $\displaystyle (-17+55k)(42) + (13-42k)(55) = 1$ (you can see that the multiples of k cancel, to leave you with the result from the previous displayed equation).

Now all you have to do is to choose k so that –17+55k lies between 100 and 200.

**For this one, start by finding x and y such that 85x+194y=1 (using Euclid's algorithm, as for Q1). Multiply the result by 12 on both sides, to give you a solution to 85X – 12 = (multiple of 19). Then add suitable multiples of 19 to find the two smallest positive values for X.**