# GCD of polynomials

In $\mathbb{Z}/5\mathbb{Z}[x]$ use the Euclidean Algorithm to find the GCD of $x^4+x^2$ and $x^4+x^3+3x$.

My thoughts: I am getting to the point where I need to use a fraction to get further in division which isint right because its not an integer. Because it is $\mathbb{Z}/5\mathbb{Z}$, I am changing any value not in $\mathbb{Z}/5\mathbb{Z}$ to the appropriate value but I am not getting anything close to a zero remainder.

-

Actually I think you were doing OK before you edited the question. You had performed your divisions, and ended up with a remainder of zero (which is what $15x$ is equal to in $\mathbb{Z}/5\mathbb{Z}$, as you realized).

A remainder of zero tells you you've just done the last step of the Euclidean algorithm. At the end of that step, what does the algorithm tell you the GCD is equal to? (It's not equal to zero, obviously ...)

The second time you tried this, you may have gotten a little less lucky in your choice of when to write, say $4$ instead of $-1$, and it may look like you can't go further without fractions, but remember, in $\mathbb{Z}/5\mathbb{Z}$, the reciprocal of each number is another number in the same set (written like an integer, not like a fraction).

To check your work, take the polynomial that the algorithm told you is the GCD, and try dividing each of your original two polynomials by that alleged GCD. If you get a remainder in either case, something went wrong. But remember to keep using $\mathbb{Z}/5\mathbb{Z}$ arithmetic. (I checked this myself, and confirmed that you had found a common divisor of the polynomials.)

There's a little ambiguity at the end because if $f(x)$ divides both of the original polynomials, then so does $-f(x)$, and in $\mathbb{Z}/5\mathbb{Z}$ you can write either one with all non-negative coefficients. I hope your instructor gave better guidance on this point than I can.

You didn't say what on-line solver you used. It sounds like it might have been finding the GCD for these polynomials in $\mathbb{Q}[x]$ rather than $\mathbb{Z}/5\mathbb{Z}[x]$.

-
yeah I finally got the answer. I wasnt taking into consideration that in the middle of all of my dividing I had to show what it was in Z(mod5) given some of the values in between dividing simply are not in Z(mod5). For example if I had -2x^2 it was really 3x^2 in Z(mod5) and I had to express it that way. thank you –  D-Man Apr 2 '14 at 3:51
Glad to hear it. Hope I gave some help and encouragement there (hint hint!). I didn't want to post the actual GCD, because I thought you'd find it much more satisfying to recognize it yourself. –  David K Apr 2 '14 at 4:04