I need to find gcd of $x^4-3x^3-2x+6$ and $x^3-5x^2+6x+7$ in $\mathbb Z/7 \mathbb Z[x]$, the integer polynomials mod $7$. Please any help will be appreciated.


In general, you use the same method as gcd of numbers: the Euclidean algorithm (detailed below). In this specific (i.e. non-general) case you can take a short-cut: since you see that the constant term in your second polynomial is $0$ mod $7$, we know that $0$ is a root mod $7$. So the second polynomial factors as $(ax^2+bx+c)x$, and we might hope there's another root. Testing, we see that $x=2,3$ are also roots, so the factorization is

$$x^3-5x^2+6x+7=x(x+4)(x+5)\mod 7.$$

Checking the first polynomial for common roots shows only $x=3$ is a common root, so $(x+4)$ is the gcd.

The more general way:


$$x^4-3x^3-2x+6=x(x^3-5x^2+6x+7)+(2x^3+x^2-2x-1)\mod 7$$ $$x^3-5x^2+6x+7=4(2x^3+x^2-2x-1)+(-2x^2+4)\mod 7$$ $$2x^3+x^2-2x-1=(-x-4)(-2x^2+4)+(2x+1)\mod 7$$ $$-2x^2+4=(-x)(2x+1)+(x+4)\mod 7$$ $$2x+1=2(x+4)+0\mod 7$$

so the gcd is $x+4$ since $2$ is a unit, though you can write $2(x+4)$ if you want, as well.

  • $\begingroup$ best answer i have got until now. thanks a lot! $\endgroup$ – user2993422 Jun 13 '15 at 20:58
  • $\begingroup$ @user2993422 glad to help, good luck with your studies! $\endgroup$ – Adam Hughes Jun 13 '15 at 21:35
  • $\begingroup$ Can the down-voter comment on what exactly he/she found wrong with my solution? $\endgroup$ – Adam Hughes Jun 17 '15 at 21:24
  • 1
    $\begingroup$ @Lokesh A gcd is only defined up to units, so it's nicer to write without the coefficient as this would just confuse the issue and make it seem like the 2 was important for some reason. $\endgroup$ – Adam Hughes Dec 7 '17 at 15:55
  • 1
    $\begingroup$ @Lokesh then I would do a bit more reading. The comment section after an answer isn't the best place to learn the basics of how units work and other conventions. Once you get a little bit more familiar with the material, my answer should make more sense :-) $\endgroup$ – Adam Hughes Dec 7 '17 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.