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 $10x + 13y = 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

[AI-generated answer — Bot GPT 3.5]

The Euclidean algorithm involves finding the greatest common divisor of 10 and 13, and then working backwards to express that gcd as a linear combination of 10 and 13.

The greatest common divisor of 10 and 13 is 1, so we know that there exists integers $x$ and $y$ such that $10x + 13y = 1$.
We can use the extended Euclidean algorithm to find $x$ and $y$:

\begin{align*}
13 &= 10(1) + 3 \\
10 &= 3(3) + 1
\end{align*}

Now, working backwards:

\begin{align*}
1 &= 10 - 3(3) \\
&= 10 - (13 - 10(1))(3) \\
&= 10(4) - 13(3)
\end{align*}

Therefore, $x = 4$ and $y = -3$. But we want the smallest possible positive value of $x$, so we add 13 to $x$ to get $x = 4 + 13 = 17$. This gives us the solution with the smallest positive value of $x$.

So the integers $x$ and $y$ that satisfy $10x + 13y = 1$ with the smallest possible positive value of $x$ are $x = 17$ and $y = -3$.

Therefore, the answer is $\boxed{17, -3}$.