3

I'm working on an assignment dealing with $\gcd$'s between 2 polynomials in some $\mathbb{Z}_n[x]$. Now I've solved most of it and it's all straight forward, except for this particular problem: $$A(x) = 2x^3 + x^2 + 1 \quad\mbox{ and }\quad B(x) = x^5 + x^4 + 2x^2 + 1\quad \mbox{ in $\mathbb{Z}_3[x]$}.$$

Now, when you start the procedure by long division, from the first step (dividing $x^5$ by $2x^3$) you get $1/2x^2$, $1/2$ is not an integer and we're in $\mathbb{Z}_3$ so there's something wrong, and it is not an integer that I can convert back to an element in $\mathbb{Z}_3$ using modulo.

Am I doing something wrong or is there a way to get around this?

Robert Z
  • 145,942

1 Answers1

4

Note that $\frac 12$ is a notation we use for the multiplicative inverse of $2$. That is, all we want from $\frac 12$ is that $$ \frac 12 \cdot 2 = 2 \cdot \frac 12 = 1 $$ So we have to find an $x \in \mathbf Z/(3)$ such that $$ 2 \cdot x = x \cdot 2 = 1 \in \mathbf Z/(3) $$ But $x=2$ fulfills that, hence in $\mathbf Z/(3)$ we have $$ \frac 12 = 2^{-1} = 2 \in \mathbf Z/(3) $$

martini
  • 84,101
  • Note that a similar thing is true for $\sqrt{{}\cdot{}}$, for instance if you want to find the roots of a quadratic equation. $\frac{-b\pm\sqrt{b^2-4ac}}{2a}$ still works. Note that if the discriminant is $0$, then there is a double root, if the discriminant is $1$, the square root reduces to $\pm1$. If the discriminant is $2$, there are no solutions. – Arthur Dec 06 '16 at 09:51