Saturday, January 4, 2020

Bézout's identity and Extended Euclidean algorithm for polynomials

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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...