# How to calculate the gcd of two polynomials $\mod 7$

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:

Write

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

• best answer i have got until now. thanks a lot! – user2993422 Jun 13 '15 at 20:58
• @user2993422 glad to help, good luck with your studies! – Adam Hughes Jun 13 '15 at 21:35
• Can the down-voter comment on what exactly he/she found wrong with my solution? – Adam Hughes Jun 17 '15 at 21:24
• @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. – Adam Hughes Dec 7 '17 at 15:55
• @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 :-) – Adam Hughes Dec 7 '17 at 16:34