Question

Use the euclidean algorithm to find integers $x$ and $y$ such that $164x + 37y = 1,$ with the smallest possible positive value of $x$. state your answer as a list with $x$ first and $y$ second, separated by a comma.

Answer 1

Well, let's use the Euclidean algorithm:

164 = 4×37 + 16

37 = 2×16 + 5

16 = 3×5 + 1

Then working backwards,

1 = 16 - 3×5

1 = 16 - 3×(37 - 2×16) = 7×16 - 3×37

1 = 7×(164 - 4×37) - 3×37 = 7×164 - 31×37

so that x = 7 and y = -31.