# Inverse of polynomial over a finite field

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

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.

• Wow dude! I can't say anything but thank you. I didn't notice that equivalences in $\mathbb{Z}_3$. Thank you very much :) – Bernat Pedrol Vozmediano Nov 5 '19 at 11:33
• @BernatPedrolVozmediano Taking the negative of a number is the same as multiplying by $-1$, and dividing by $5 = -1$ is the same thing. So taking the negative and dividing by $5$ cancel, and we get $-\frac15 = 1$. – Arthur Nov 5 '19 at 11:59

Hint: $$0=x^2 + 2x + 2$$ implies $$0 = 2x^2+4x+4 = 2x^2+x+1 = x(2x+1)+1$$

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