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://imgur.com/a/8Wku6 (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


1 Answer 1


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). $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.