Question

Show in fact that 1=9m + 20n for some integers m and n

Answer 1

`1=9\cdot 9+20\cdpt (-4)=81-80`

Explanation:

The greatest common divisor between 9 and 20 is 1, so we know the equation
`1=9m+20n` has a solution. A solution can be found either by inspection, or by applying Euclidean algorithm.

By inspection we just list some multiples of 9:

9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99

and also list some mutiples of 20:

20, 40, 60, 80, 100, 120

And so we see that we can find a multiple of 9 (81) which is 1 away from a multiple of 20 (80). Which is the solution given at the start.

For the Euclidean algorithm, we should divide the greatest of the two numbers, by the smallest one, and keep track of the remainder:

20 = 9 * 2 + 2

Then we divide 9 by the remainder we got, which is 2:

9 = 2 * 4 + 1

we would continue doing this until getting a remainder of 1 (which we just did). Finally we "solve" for 1, from the last equation:

9 - 2*4 = 1

And then we solve for 2 from the first equation, and plug that in into the previous equation:

20 - 9*2 =2

9 - ( 20 - 9*2)*4 = 1

which does give us the same solution:
`9\cdot 9 +20\cdot (-4)=1`