4
$\begingroup$

Find out if polynomial $x^3-x^2+x-1$ has inverse element in quotient ring ${\displaystyle \mathbb {Z} }_{11}/(x^4+3x^3-3x^2-4x-1)$, if yes find this inverse.

I know that $x^3-x^2+x-1$ has inverse element when $gcd(x^4+3x^3-3x^2-4x-1;x^3-x^2+x-1)$~$1$. I also know that I can use Euclidean algorithm. But I'm not sure about my result, I have got result that the g$cd$~$5$ it means that $x^3-x^2+x-1$ does not have inverse. Am I correct?

Thanks for any help!

$\endgroup$
0
3
$\begingroup$

I did not check the computations, but if you got $5$, then that means that they are relatively prime and therefore that it has an inverse. That's so because asserting that $5$ is a greatest common divisor of two polynomials is the same thing as asserting that $1$ is a greatest common divisor of them. Note that, in $\mathbb{Z}_{11}$, $5\neq0$.

$\endgroup$
2
  • $\begingroup$ Thanks very much, I am trying to find inverse, I have found that it should be $5x^3+3x^2+2x+3$, if I haven't made a mistake. If it isn't correct result I can edit contribution, and write down my process. I am little confused, how can I chcek if my inverses is correct, sorry about my simple questions. $\endgroup$
    – Tomak
    Jun 11 '18 at 14:59
  • $\begingroup$ @Tomak You check by computing the product of the original polynomial by the one that you got. You should get $1$ modulo $x^4+3x^3-3x^2-4x-1$. $\endgroup$ Jun 11 '18 at 15:03
3
$\begingroup$

The extended Euclidean algorithm over $\mathbb Q$ gives: $$ 232 = (49 x^3 + 168 x^2 - 75 x - 195)(x^3-x^2+x-1) +(-49 x^2 + 28 x - 37)(x^4+3x^3-3x^2-4x-1) $$ Mod $11$, this becomes $$ 1 \equiv (5 x^3 + 3 x^2 - 9 x - 8)(x^3-x^2+x-1) \bmod (x^4+3x^3-3x^2-4x-1) $$ and so the inverse is $5 x^3 + 3 x^2 - 9 x - 8 \equiv 5x^3+3x^2+2x+3$.

$\endgroup$
1
$\begingroup$

Since Jose already covered the fact that your approach is valid, I'll present a cool alternative approach. First, construct the companion matrix of $x^4+3x^3-3x^2-4x-1$, call it $A$.

Here $$A = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -3 \end{pmatrix}_.$$

Now consider the matrix, $B = A^3 - A^2 + A - I$. Then $B$ is invertible (recall that the coefficients of the matrix lie in $\mathbb{Z}_{11}$) iff $x^3 - x^2 + x - 1$ is invertible. Even stronger, if you express $B^{-1}$ as a linear combination of $I, A, A^2, A^3$, this tells you the inverse of $(x^3-x^2 + x -1)$!

More explicitly, if $B^{-1} = c_3A^3 + c_2A^2 + c_1A + c_0I$, then $$(x^3-x^2+x-1)^{-1} = c_3x^3+c_2x^2+c_1x+c_0.$$

$\endgroup$
2
  • $\begingroup$ Very beautiful, I would never think of that it can be join in this way. But what looks like little difficult for me how to find $B^{-1}$ as a linear combination. Are there some easy way? $\endgroup$
    – Tomak
    Jun 11 '18 at 18:47
  • 1
    $\begingroup$ Let me preface this by saying that you almost certainly wouldn't want to do this by hand. You can consider $I,A,A^2,A^3,$ and $B^{-1}$ as vectors of length $16$. Put the vectors corresponding to $I, A, A^2, A^3$ as the first 4 columns of a matrix, and the vector corresponding to $B^{-1}$ as the $5^{th}$ column. If you do row reduction to put this matrix in reduced row echelon form, the entries in the $5^{th}$ column will then tell you how to express $B^{-1}$ as a linear combination of the others. Again, this is not something you would want to do by hand, but a computer would be happy to do. $\endgroup$
    – Ken Duna
    Jun 15 '18 at 16:46

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.