Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I cannot find whether multiplicative inverse of $x^3+x^2+x+1 \pmod{x^5+x^4+x^3-x^2-x+1}$ over $\mathrm{GF}(3)$ exists. This problem must be solved with Extended Euclidean algorithm.

I tried to divide $x^5+x^4+x^3-x^2-x+1$ by $x^3+x^2+x+1$.

I think I divided it wrong. I got $x^2-2x-2$.

Thanks for any help

share|improve this question
    
It sounds like the task really is to find whether the coset $x^3+x^2+x+1+I$ in the ring $GF(3)[x]/I$ has a multiplicative inverse or not. Here $I$ is the ideal generated by the polynomial $x^5+x^4+x^3-x^2-x+1$. –  Jyrki Lahtonen May 27 '12 at 14:02
1  
$$x^3+x^2+x+1 = x^2(x+1)+(x+1) = (x^2+1)(x+1)$$ while $$x^5+x^4+x^3-x^2-x+1 = x^4(x+1)+x^2(x+1)+x(x+1)+(x+1) = (x^4+x^2+x+1)(x+1)$$ and so the gcd is not a constant. Of course, this is not using the Extended Euclidean Algorithm as seems to be required, but I hope the results obtained by that method will be consistent with this observation. –  Dilip Sarwate May 27 '12 at 14:27
    
If it's too much work / too error prone, then don't bother doing a complete division: you can make progress even if all you compute is the leading term of the quotient, which can be obtained by inspection. –  Hurkyl May 27 '12 at 15:19

1 Answer 1

up vote 2 down vote accepted

The problem you are trying to solve is not clearly stated, but what is clear is that you are having some difficulty with polynomial division, or (more likely) just think that you are. What probably happened is something that happens to everybody, a slip with signs.

We will do ordinary polynomial division. To start the division process, imitate school division. The polynomial $x^3+x^2+x+1$ "goes into" $x^5+x^4+x^3-x^2-x+1$ how many tines? Clearly $x^2$ times. So multiply $x^3+x^2+x+1$ by $x^2$, subtract from $x^5+x^4+x^3-x^2-x+1$. The raw remainder we get is $-2x^2-x+1$. Since we are working over the $3$ element field, this can be rewritten in various ways. It is sensible to replace the $-2$ by $1$, obtaining remainder $x^2-x+1$, or $x^2+2x+1$.

If negatives give you trouble, you could start by replacing $x^5+x^4+x^3-x^2-x+1$ by $x^5+x^4+x^3+2x^2+2x+1$.

Anyway, we have quotient $x^2$, remainder $x^2-x+1$. Continue the Euclidean algorithm process by dividing $x^3+x^2+x+1$ by $x^2-x+1$. You should get quotient $x+2$ (or $x-1$), remainder some version of $2x-1$. Continue.

share|improve this answer
1  
Yet the OP's title is "existence of multiplicative inverse"...the only pol's that are invertible over a field are the constant ones. –  DonAntonio May 27 '12 at 13:41
1  
@DonAntonio I thought the possibility of an inverse of a polynomial in the ring $\mathbb F_3[x]/(x^5+x^4+x^3-x^2-x+1)$ was under investigation, not an inverse over a field. –  Dilip Sarwate May 27 '12 at 14:57
    
@Dilip But then it is not the mult. inverse of "a polynomial" in that field, but of an element of it which, I agree, can be represented by a polynomial-like element... –  DonAntonio May 27 '12 at 18:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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