Find integers $x,y$ such that $21x + 13y = 1$

Question

Given Bézout's identity, how do I find the $x,y$, I already performed the euclidean algorithm. So.

• 21 = 1 * 13 + 8
• 13 = 1 * 8 + 5
• 8 = 1 * 5 + 3
• 5 = 1 * 3 + 2
• 3 = 1 * 2 + 1
• 2 = 1 * 1 + 1
• 1 = 1 * 1 + 0

I am not sure how to find the x,y though I tried starting from 1 = 2 - 1 and then substituting 2 as 3 - 1 and so on but I wasn't getting anywhere I know I need to somehow get 21*some number + 13 * some number but I am confused on how to start.

Answer 1

(Using the extended Euclidean algorithm, not Fibonacci identities)

$1=3-2=3-(5-3)=2\cdot3-5=2\cdot(8-5)-5=2\cdot8-3\cdot5=2\cdot8-3\cdot(13-8)=5\cdot8-3\cdot13=5\cdot(21-13)-3\cdot13=5\cdot21-8\cdot13$

Answer 2

Use the extended Euclidean algorithm: it relies on the fact that all remainders in the Euclidean algorithm, satisfy a Bézout's identity, and corresponding coefficients can be computed recursively.

\begin{array}{rrrl} r_i&x_i&y_i &q_i\\ \hline 21&1&0 \\ 13&0&1&1 \\ \hline 8&1&-1&1\\5&-1&2&1 \\ 3&2&-3&1 \\ 2&-3&5&1 \\ \hline 1&\color{red}5&\color{red}{-8} \end{array}