2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow dude! I can't say anything but thank you. I didn't notice that equivalences in $\mathbb{Z}_3$. Thank you very much :) $\endgroup$ – Bernat Pedrol Vozmediano Nov 5 '19 at 11:33
  • $\begingroup$ @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$. $\endgroup$ – Arthur Nov 5 '19 at 11:59
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.