Answer to Question #181322 in Discrete Mathematics for zhixi

Question

Use the Euclidean algorithm to find integers 𝑥 and 𝑦 such that 2640𝑥 + 2110𝑦 = 10

Answer 1

Let us use the Euclidean algorithm to find integers $𝑥$ and $𝑦$ such that $2640𝑥 + 2110𝑦 = 10$. This equation is uquivalent to the equation $264𝑥 + 211𝑦 = 1$.

Since

$264=211\cdot 1 +53, \ 211=53\cdot 3+52, \ 53=52\cdot 1+ 1,$

we conclude that

$1=53-52=53-(211-53\cdot 3)=-211+53\cdot 4=-211+(264-211)\cdot 4=264\cdot 4+211(-5).$

Therefore, $x=4$ and $y=-5$.

The general solution of the equation is $\begin{cases} x=4-211t\\ y=-5+264t \end{cases}$