Question

As shown in class, the Euclidean algorithm can be used to find solutions to equations of the form
ax + by = c


Use the Euclidean algorithm to find integers $x$ and $y$ such that $6x + 5y = 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.



Note that while there are many pairs of integers $x$ and $y$ that satisfy this equation, there is only one pair that comes from using the Euclidean algorithm as described in class, and this pair solves the problem.

Answer 1

The Euclidean algorithm involves finding the greatest common divisor (gcd) of the two coefficients, in this case 6 and 5.

Using the Euclidean algorithm:
$6 = 1 \times 5 + 1$
$5 = 5 \times 1$

This gives us the equation in terms of the gcd:
$1 = 6 - 1 \times 5$

Therefore, the integers $x$ and $y$ that satisfy $6x + 5y = 1$ are $x = -1$ and $y = 1$. However, since we are asked for the smallest positive value of $x$, we can add 5 to x to make it positive:
$x = 4, y = -3$

So the solution is $\boxed{4, -3}$.