# Find the coefficients in Euclid's algorithm

$a(x)=3x^4-4x^3-11x^2+4x+9$

$b(x)=3x^3+5x^2+x-1$

I find the greatest common divisor: $$\frac {3x^4-4x^3-11x^2+4x+9}{3x^3+5x^2+x-1}=x-3 \;\ \;\ mod= 3x^2+8x+6$$ $$\frac {3x^3+5x^2+x-1}{3x^2+8x+6}=x-1 \;\ \;\ mod= 3x+5$$ $$\frac {3x^2+8x+6}{3x+5}=x+1 \;\ \;\ mod= 1$$

Greatest common divisor $= 1$

I am looking for coefficients using the extended Euclidean algorithm, table:

$3x^4-4x^3-11x^2+4x+9 \;\ \;\ \;\ \;\ 1 \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ 0$

$3x^3+5x^2+x-1 \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ 0 \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ 1$

$3x^2+8x+6 \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ 1 \;\ \;\ \;\ \;\ -x+3$

$3x+5 \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ -x+1 \;\ \;\ \;\ \;\ \;\ \;\ ?$

$1 \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\ \;\$?$\;\ \;\ \;\ \;\ \;\ \;\ \;\$?

Checking: a(x)$(3x^4-4x^3-11x^2+4x+9)+$b(x)$(3x^3+5x^2+x-1)=1$

## 1 Answer

In general, $a = bq+r$, so $1 \cdot a + (-q) \cdot b = r$. To continue the calculations, we introduce the notation $(\alpha,\beta)$ to denote $\alpha \cdot a + \beta \cdot b$, so that it's convenient to calculate the linear combinations of $a$ and $b$. Therefore, $r$ becomes $(1,-q)$.

In the Extended Euclidean Algorithm, since $r_{i+1} = r_{i-1} - q_ir_i$, we have \begin{aligned} (\alpha_{i+1},\beta_{i+1}) &= (\alpha_{i-1},\beta_{i-1}) - q_i(\alpha_i,\beta_i) \\ &= (\alpha_{i-1}-q_i\alpha_i,\beta_{i-1}-q_i\beta_i). \end{aligned}

The follow table illustrates the calculations for $\alpha_{i+1}$ and $\beta_{i+1}$ from the last two rows. \begin{array}{|r|r|r|r|}\hline \text{index} & \text{quotient } q_{i-1} & \hfill \text{remainder } r_i \hfill & \alpha_i & \beta_i \\ \hline i-1 & q_{i-2} & r_{i-1} & \color{red}{\alpha_{i-1}} & \color{red}{\beta_{i-1}} \\ \hline i & q_{i-1} & r_i & \color{blue}{\alpha_i} & \color{blue}{\beta_i} \\ \hline i+1 & \color{blue}{q_i} & r_{i+1} & \color{red}{\alpha_{i-1}}-\color{blue}{q_i\alpha_i} & \color{red}{\beta_{i-1}}-\color{blue}{q_i\beta_i} \\ \hline \end{array}

From your (correct) calculations for the Euclidean Algorithm, the first few rows of the following table are fixed.

\begin{array}{|r|r|r|r|}\hline \text{index} & \text{quotient } q_{i-1} & \hfill \text{remainder } r_i \hfill & \alpha_i & \beta_i \\ \hline 1 & & 3x^4-4x^3-11x^2+4x+9 & 1 & 0 \\ \hline 2 & & 3x^3+5x^2+x-1 & 0 & 1 \\ \hline 3 & x-3 & 3x^2+8x+6 & 1 & -x+3 \\ \hline 4 & x-1 & 3x + 5 & -x+1 & x^2-4x+4\\ \hline 5 & x+1 & 1 & x^2 & -x^3+3x^2-x-1\\ \hline \end{array}

Checking: \begin{aligned} & x^2 (3x^4-4x^3-11x^2+4x+9) + (-x^3+3x^2-x-1)(3x^3+5x^2+x-1) \\ &= 3x^6-4x^5-11x^4+4x^3+9x^2 + (-3x^6+4x^5+11x^4-4x^3-9x^2+1) \\ &= 1 \end{aligned}