0
$\begingroup$

How do you calculate the multiplicative inverse of a polynomial mod a monomial/integer?The specific questions are: Find the multiplicative inverse of 1) x+1 mod 3 2) x^2+x-1 mod 3 3) x^2+x-1 mod 32

I understand that you need to use the Extended Euclidean algorithm to solve it. For integer mod integer (e.g. 11 mod 26) and polynomial mod polynomial, its clear.But how to solve x+1 mod 3?

$\endgroup$
0
$\begingroup$

Neither $x+1$ nor $x^2+x-1$ are invertible modulo $3$, i.e. in the polynomial ring $\mathbf Z/3\mathbf Z[x]$, which is a polynomial ring over a field, because in such a case, for any polynomials $f,g$ we have $\deg fg=\deg f+\deg g \ge\deg f,\deg g$, which is not compatible with $fg=1$ unless $f$ and $g$ are constants.

If the quotient ring is not a field, this may not be true. However $x^2+x-1$ invertible in $ is impossible since its dominant coefficient is $1$, hence $\deg f(x)(x^2+x-1)=\deg f+2$.

For an example with coefficients in $\mathbf Z/32\mathbf Z$ you can check that $\;(16x^2-4x+1)(4x+1)=1$.

$\endgroup$
  • $\begingroup$ Thank you for the response. $\endgroup$ – jaynjayn Jul 14 '15 at 16:06
  • $\begingroup$ do you mean that for a polynomial f to have a multiplicative inverse mod g then inlinedeg fg=deg f+deg g ≥deg f,deg g ? If that is the case then x+1 mod 3 meets the criteria because deg ((x+1)3)=1' and deg f=1` and deg g=0 . Kindly explain $\endgroup$ – jaynjayn Jul 15 '15 at 7:03
  • $\begingroup$ If $fg=1$, we must have $\deg f+\deg g=\deg 1=0$, whence $\deg f=\deg g=0$, i. e. $f$ and $g$ must be non-zero constants. $\endgroup$ – Bernard Jul 15 '15 at 7:29

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.