1

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.

Bernard
  • 175,478
iceiscold
  • 39

2 Answers2

3

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}

J. W. Tanner
  • 60,406
Bernard
  • 175,478
  • 1
    How does this chart work, it looks simpler to write. – iceiscold Dec 17 '20 at 23:38
  • 1
    You simply rewrite the $i$-th division: $r_{i-1}=q_ir_i+r_{i+1}$ as $r_{i+1}=r_{i-1}-q_ir_i$ and observe that by lienarity the same relation is valid for the coefficients: $x_{i+1}=x_{i-1}-q_ix_i ,\enspace y_{i+1}=y_{i-1}-q_iy_i$. – Bernard Dec 17 '20 at 23:44
2

(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$

J. W. Tanner
  • 60,406