Bézout's coefficients, modular inverse

Question

I have to find $14^{-1} (\mod 17)$

I made the equation, $$14x+17y=1$$ By Euclidean division algorithm- $$ 17=14\times1+3 \\ 14=3\times4 +2\\3=2\times1+1$$ If I reverse the process then, $$1=3-2\times1 \\=3-(14-3\times4)\times1 \\= 3-[14-(17-14\times1)\times4]\times1$$

But this doesn't seem to in the required form...

What have I done wrong?

Answer 1

Everything is right so far. You just need to note that $3 = 17 - 14$, so you have:

$$1 =(17-14)-[14-(17-14\times1)\times4]\times1$$ $$=(17-14)-[14-(17-14)\times4]$$ $$=(17-14)-[14-(17 \times 4-14\times 4)]$$ $$=(17-14)-[-17 \times 4 \color{red}{+}14 \times 5]$$ $$=(17-14) + 17 \times 4 -14 \times 5]$$ $$=17 \times 5-14 \times 6$$

Answer 2

You'd better use the standard layout of the extended Euclidean algorithm, which is based on the observation that all remainders are linear combinations of $14$ and $17$:

\begin{array}{rrrr} r_i &u_i&v_i&q_i \\ \hline 17&0&1\\ 14&1&0&1\\ \hline 3&-1&1&4 \\ 2&5&-4&1 \\ 1&\color{red}{-6}&\color{red}{5} \\ \hline \end{array}

(results inductively from the relation $r_{i-1}=q_ir_i+r_{i+1}$, rewritten as $$r_{i+1}=r_{i-1}-q_ir_i)$$