Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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