Polynomial division modulo 5, gcd of two polynomials
I have to find the gcd $h$ of $f$ and $g$ in $\mathbb{F}_5[X]$.
$f=X^9+X^8+X^7+X^6+X^5+X^4+X^3+X^2+X+1,$
$g=X^4+X-2.$
Here is my polynomial division:
My solution is $3X^3-X^2+3X+1$ but this is not correct, because I have to use it for further tasks and it doesn't work there. In addition, wolfram alpha says the solution in modulo 5 is $X^2+3X+1$ and I can solve the other tasks with this polynomial.
Can someone please check my polynomial division?
$\endgroup$ 93 Answers
$\begingroup$First I divided $X^9$ by $X^4$ and wrote $X^5$ right next to the equal sign. Then I subtracted $X^5\times (X^4+X-2)$ from $(X^9+X^8+...+X^2+X+1)$ and wrote the result below. Then the same step over and over again, i.e. dividing $X^8$ by $X^4$, adding the result to the right and multiplying it back. I did this until the degree is smaller than $X^4$. This should be the correct result, but unfortunately it is not. This should be the standard algorithm for polynomial long division ().
$\endgroup$ 0 $\begingroup$Notice that in mod $5$, $$g=x^4+x-2=(x-1)^2(x^2+2x+3).$$On the other hand, the polynomial $f$ also has $x-1$ as a factor since $f(1)=0$. Also $f'(1)=45=0\pmod 5$. Therefore $\gcd(f,g)$ contains $(x-1)^2=x^2+3x+1$ as a factor.
Now we only need to show that $x^2+2x+3$ is not a factor of $f$.
$\endgroup$ 3 $\begingroup$- There's an error in your final step. The result should be $\ 3x^3-x^2+3x \ $.
- You haven't completed the computation. The result $\ 3x^3-x^2+3x \ $ is simply the remainder of $\ \sum_\limits{k=0}^9x^k\ $ on division by $\ x^4+x-2\ $. You now have to find the remainder of $\ x^4+x-2\ $ on division by $\ 3x^3-x^2+3x \ $. Subtracting $\ 2x\left(3x^3-x^2+3x\right)\ $ from $\ x^4+x-2\ $ gives you $\ 2x^3-x^2+x-2\ $, and adding $\ 3x^3-x^2+3x \ $ to this gives you $\ 3x^2+4x-2=3(x^2+3x+1)\ $—that is, the result returned by Wolfram alpha multiplied by the unimportant factor of $3$.
This doesn't quite complete the procedure, however. You still have to find the remainder of $\ 3x^3-x^2+3x \ $ on division by $\ x^2+3x+1\ $, which you should find to be $0$, thus telling you that $\ x^2+3x+1\ $ is the desired gcd.
$\endgroup$ 4
