TITLE: Inverse of polynomial over a finite field
QUESTION [2 upvotes]: The question is the following:
Can you deduce if ${2x + 1}$ is invertible in $\mathbb{Z}_3[x]/(x^2 + 2x + 2)$? In case of a positive answer, give its inverse.
Following the Wilson's theorem, for $K[X]/(f)$, any polynomial of degree $1 \leq deg < n$ will admit an inverse of degreee $1 \leq deg \leq n$ mod $f$. Since $n = 3$ because I'm working on $\mathbb{Z}_3$ and $deg = 2$, I guess $2x+1$ is irreductible in this case.
Once I want to find the inverse I've been following this post. The table using Euclidean algorithm is the following:
\begin{array}{r|r|r|r}
    & & (x+\frac{3}{2})/2 & (2x+3)/5 \\\hline
   1 & 0 & 1 & -(2x+3)/5\\\hline
   0 & 1  & -\big(\dfrac{x}{2} + \dfrac{3}{4}\big) & \dfrac{x^2}{5} + \dfrac{3x}{5} + \dfrac{29}{20}\\\hline
   x^2+2x+2 & 2x+1 & 5/4 & 0
\end{array}
So, finding the lineal combination I obtain this result:
$\dfrac{5}{4} = 1\times(x^2 +2x +2) - \big(\dfrac{x}{2}+\dfrac{3}{4}\big)\times(2x+1)\xrightarrow{}\dfrac{5}{4} = f(x) - \big(\dfrac{x}{2}+\dfrac{3}{4}\big)g(x)$,
Here is where I get stuck. I let 1 on the left side so I have the following result:
$1 = \bigg(\dfrac{4}{5}\bigg)(x^2+2x+2)- \bigg(\dfrac{2x}{5}+\dfrac{3}{5}\bigg)(2x+1)$
But once I arrive here I don't know how to get the value of the inverse.
Can anyone help me? Thank you very much.
My result, which I'm not absolutely sure is that the inverse of $2x+1$ is:
$-\big(\dfrac{2x}{5}+\dfrac{3}{5}\big)$ mod $x^2+2x+2$.
In the remote case it's correct, is there any way to get the final value instead of letting it in function of mod $f$?
Thank you again.
Bernat

REPLY [3 votes]: Note that $-\frac15 = 1$ in $\Bbb Z_3$, and $3 = 0$, so your inverse candidate is equal to $2x$. And we can just check whether this is in fact an inverse, using that $3 = 0$ and $x^2 = x+1$:
$$
2x\cdot (2x+1) = 4x^2 + 2x = 4(x+1) + 2x\\
= 6x + 4 = 1
$$
So yes, that is indeed the inverse you're looking for.

REPLY [1 votes]: Hint: $0=x^2 + 2x + 2$ implies $0 = 2x^2+4x+4 = 2x^2+x+1 = x(2x+1)+1$

REPLY [0 votes]: Since $\mathbb{Z}/3\mathbb{Z}$ is a field, we know that $\mathbb{Z}/3\mathbb{Z}[x]$ is an Euclidean domain with norm, $\deg f(x)$.
From now, I'll have worked with your example.
We can find $p(x), q(x) \in \mathbb{Z}/3\mathbb{Z}[x]$ which satisfies
$$
(x^2+2x+2) p(x) + (2x + 1)q(x) = 1  
$$
It holds if $p(x) = 2, q(x) = -x$.
It means that
$$
(2x + 1)(-x) \equiv 1 \mod x^2+2x +2
$$
{"set_name": "stack_exchange", "score": 2, "question_id": 3422864}