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



a(x)=x4+1m(x)=x3+3x+1d(x)=gcd(a(x),m(x))



I found d(x) by using Euclidean algorithm
x4+1=(x3+3x+1)x(3x2x+1)x3+3x+1=(3x2x+1)(x3+19)+(31x9+89)3x2x+1=(31x9+89)(27x3163961)+1017961



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 (x3+3x+1)(31x3113+8x211313x113+7113)+(x4+1)(31x21138x113+106113)=1



Where U=(31x3113+8x211313x113+7113)


V=(31x21138x113+106113)




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:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...