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
No comments:
Post a Comment