I'm trying to find the $U, V$ such that $a(x)U + m(x)V = d(x)$.
\begin{align*} a(x) &= x^4+1\\ m(x) &= x^3+3x+1\\ d(x) &= \gcd(a(x),m(x)) \end{align*}
I found $d(x)$ by using Euclidean algorithm \begin{align*} x^4+1 &= (x^3+3x+1) \cdot x -(3x^2-x+1)\\ x^3+3x+1 &= (-3x^2-x+1) \cdot (\frac{-x}{3}+\frac{1}{9}) + (\frac{31x}{9}+\frac{8}{9})\\ -3x^2-x+1 &= (\frac{31x}{9}+\frac{8}{9})\cdot (\frac{-27x}{31} - \frac{63}{961})+ \frac{1017}{961}\\ \end{align*} so because the remainder is equal to a constant, $d(x)= 1$.
Then I try to solve the equation $a(x)U + m(x)V = d(x)$ by using the Extended Euclidean algorithm, and more precisely by using the table (shown here: https://www.numbertheory.org/php/euclid.html)
and with all the values put in the table looks like this: https://i.stack.imgur.com/ZrVxA.jpg (sry I don't know how to put tables into stackexchange)
I know the answer should be $(x^3+3x+1) \cdot (-\frac{31x^3}{113}+\frac{8x^2}{113}- \frac{13x}{113}+\frac{7}{113}) + (x^4+1) \cdot (\frac{31x^2}{113} - \frac{8x}{113} + \frac{106}{113}) = 1$
Where $$ U = (-\frac{31x^3}{113}+\frac{8x^2}{113}- \frac{13x}{113}+\frac{7}{113})$$ $$ V = (\frac{31x^2}{113} - \frac{8x}{113} + \frac{106}{113}) $$
But I don't know what I'm doing wrong with my Euclidean algorithm or Euclidean extended algorithm.
Thanks in advance
I don't really understand what your table stands for. You have \begin{align*} x^4+1 &= (x^3+3x+1) \cdot x +(-3x^2-x+1)\\ x^3+3x+1 &= (-3x^2-x+1) \cdot (-\frac{x}{3}+\frac{1}{9}) + (\frac{31x}{9}+\frac{8}{9})\\ -3x^2-x+1 &= (\frac{31x}{9}+\frac{8}{9})\cdot (\frac{-27x}{31} - \frac{63}{961})+ \frac{ {1017}}{961}.\\ \end{align*} Collecting results,
\begin{align} \frac{1017}{961}&=-3x^2{+}x+1- (\frac{31x}{9}+\frac{8}{9}) (-\frac{27x}{31} -\frac{63}{961})\\ \ \\ &=-3x^2{+}x+1- \left(x^3+3x+1-(-3x^2-x+1)(-\frac x3+\frac19) \right) (-\frac{27x}{31} - \frac{63}{961})\\ \ \\ &= \left(x^3+3x+1\right)(\frac{27x}{31} + \frac{63}{961})+(-3x^2-x+1)\left((-\frac x3+\frac19) (-\frac{27x}{31} + \frac{63}{961})+1\right)\\ \ \\ &= \left(x^3+3x+1\right)(\frac{27x}{31} + \frac{63}{961})+(x^4+1-(x^3+3x+1)x)\left(\frac{9x^2}{31}-\frac{72x}{961}+\frac{954}{961}\right)\\ \ \\ &=(x^4+1)\left(\frac{9x^2}{31}-\frac{72x}{961}+\frac{954}{961}\right) +(x^3+3x+1)\left(-\frac{9x^3}{31}+\frac{72x^2}{961}-\frac{117x}{961}+\frac{63}{961} \right). \end{align} Now using that $1017=9\times 113$ and $961=31^2$, we get $$ 1=(x^4+1)\left(\frac{31x^2}{113}-\frac{8x}{113}+\frac{106}{113}\right) +(x^3+3x+1)\left(-\frac{31x^3}{113}+\frac{8x^2}{113}-\frac{13x}{113}+\frac{7}{113} \right). $$