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−(3x2−x+1)x3+3x+1=(−3x2−x+1)⋅(−x3+19)+(31x9+89)−3x2−x+1=(31x9+89)⋅(−27x31−63961)+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+8x2113−13x113+7113)+(x4+1)⋅(31x2113−8x113+106113)=1
Where U=(−31x3113+8x2113−13x113+7113)
V=(31x2113−8x113+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