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?
Best Answer
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 leading 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$.