Question

1) Use the Euclidean Algorithm to nd the greatest common divisor of 71407 and 2020. (Write down all of the steps, so that you are ready).

2) Use the method of back substitution to nd integers x; y such that 71407x + 2020y = d, where d = gcd(71 407, 2020).
3) Use the array method to solve the equation in (b).
4) Explain, why there is no solution in integer numbers of the equation 71407x + 2020y = 1?

Answer 1

Explanation:

We have

`71407 = 2000(35)+1407\\2000 = 1407+1(593)\\1407= 2(593) + 221\\593 = 2(221) = 151\\221=151+70\\151=2(70)+11\\70 = 6(11)+4\\11=2(4)+3\\4 = 3+1\\3 = 3(1)+0\\`

So we find GCD = 1

2) By back substitution we get

71407 (543) - 19387(2000) =1

So x = 543 and y = -19387

Because we got 71407 (543) - 19387(2000) =1

y cannot be positive

y can only be negative