# find the GCD of two polynomials of equal degree

Q: Find the GCD of the polynomials $x^3 + 4$ and $x^3 + 4x^2 + x +3$ modulo $7$.

The problem I found is that this question doesn't elaborate on modulo or which polynomial to use if both are of equal degree?

As this is for homework, I would prefer working out however as a guidance so please no explicit answer unless added as a spoiler.

-
Do you know the Euclidean algorithm? –  Daniel Montealegre Apr 19 '12 at 4:21
@DanielMontealegre Yes, we're taught to do long division then EA. –  Taz Apr 19 '12 at 4:24
In this case, “modulo $7$” means that you are to think of the coefficients as not integers or real numbers, but as objects in the ring ${\mathbb{Z}}/(7)$. If you know how to calculate the gcd of the two given polynomials over the reals, you can do it in the system of the integers modulo $7$. –  Lubin Apr 19 '12 at 4:24
As for writing in 'math' (the software used here is known as $\TeX$), just put dollar signs around the mathematical expressions in your post. –  Brett Frankel Apr 19 '12 at 4:28

$\gcd (f(x),g(x))=\gcd(f(x), g(x)+uf(x))$, where $u$ is any unit. If you subtract one polynomial from the other, the result will be of lower degree. Now you can apply the Euclidean algorithm as you learned it (or as described in the post you linked to).
I'm still having a few issues working it out. So, as you said I should do $(x^3 + 4^2 + x +3) - (x^3 + 4) = (4x^2 + x -1)$ However EA is in the form of abc = (a)*(b)+(c)? –  Taz Apr 19 '12 at 7:10
Hint $\rm\ mod\ 7\!:\ c\not\equiv 0\:\Rightarrow\: c^6\equiv 1\:\Rightarrow\: c^3 \equiv\: \pm1 \not\equiv -4,\:$ so $\rm\:x^3+4\:$ is irreducible mod $\rm\ 7$.