GCD of polynomials

179 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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