Extended Euclidean Algorithm to find modular multiplicative inverse of polynomial in $\mathbb{Z}_m[X]/P(X)$ if m is not prime?

Question

I'm looking into modular polynomial rings over the integers (if that's the right term?) i.e. $\mathbb{Z}_m[X]/P(X)$ where $\mathbb{Z}_m$ is the ring of integers modulo m, and P(X) is some polynomial with coefficients in $\mathbb{Z}_m$. Note that m is not necessarily prime so $\mathbb{Z}_m[X]$ may not be a field.

I wish to understand how to calculate the multiplicative inverse of polynomials (or should I call it polynomial classes) in such rings. I think I understand how to use the Extended Euclidean Algorithm, which works fine if m is prime. But if m is not prime I run astray.

For example: say R=$\mathbb{Z}_4[X]/(X^3-1)$ and find the inverse of $2x+1$ in R.
I know that the solution is $2x+1$, since $(2x+1)^2=1$ in R.
But right in the first step I need to multiply $2x+1$ with something and subtract that from $x^3-1$ to reduce its degree. But this is impossible since 2 is invertible (mod 4).

Another example: same R=$\mathbb{Z}_4[X]/(X^3-1)$ and find the inverse of $3x^2+2x+2$ in R.
I know that the solution is $2x^2+3x+2$, since $(3x^2+2x+2)\cdot(2x^2+3x+2)=1$ in R.
In the first step I multiply $3x^2+2x+2$ by $3x$ and subtract that from $x^3-1$ which leaves $2x2+2x+3$. And now I run into the same problem.

Am I doing it wrong, or is there a better way to either find an inverse in such cases or find that it doesn't exist?

Answer 1

Given $f\in \Bbb{Z}[x]/(p^2,U)$ using the extended euclidean algorithm find some $g$ (if it exists, otherwise $f$ is not a unit) such that $fg=1\in \Bbb{Z}[x]/(p,U)$

So there is some $r$ such that $fg=1+pr$ in $\Bbb{Z}[x]/(p^2,U)$.

The inverse of $f\in \Bbb{Z}[x]/(p^2,U)$ is of the form $g+ph$.

Since $f(g+ph) = 1+p r+fph$, we want $fph=-pr$ in $\Bbb{Z}[x]/(p^2,U)$ ie. $fh =-r$ in $\Bbb{Z}[x]/(p,U)$,

ie. $h = -rg$ in $\Bbb{Z}[x]/(p,U)$ and the inverse of $f$ in $\Bbb{Z}[x]/(p^2,U)$ is $$g-prg$$

It works the same way, repeating the same idea $n$ times, for finding the inverse of $f\in \Bbb{Z}[x]/(p^n,U)$.

For the inverse of $f\in \Bbb{Z}[x]/(m,U)$ factorize $m$ in prime powers, solve for the inverse modulo each prime power, then mix the inverses using the isomorphism $\Bbb{Z}[x]/(m,U)\to \prod_j \Bbb{Z}[x]/(p_j^{n_j},U)$.

Answer 2

There is a version of Buchberger's algorithm to find Groebner bases of ideals of $\mathbb{Z}[x]$. (Where in this case, the "initial term" of a polynomial includes the coefficient, as opposed to the case of Buchberger's algorithm for polynomials over a field.) For the special case of a single variable over $\mathbb{Z}$, the algorithm can be stated as follows: keep a list of generators sorted by increasing degree, and then by increasing absolute value of coefficient of the initial term. At each step, multiply one of the elements by $x$ raised to the difference between that generator's degree and the degree of the next element in the list. Then, repeatedly subtract powers of $x$ times previous elements to reduce to the smallest initial term possible. If at the end, you still have a nonzero polynomial, then add it to the generating set. An alternate move, if you have any element whose leading term has a larger initial coefficient than any previous term, is to do the reduction modulo previous terms as above; if you end up with zero, you can remove the element, and otherwise you can replace the element with the remainder. Once you have a situation where none of these moves changes the list, you have a Groebner basis.

For an example, let us use this to find an inverse of $3x^2 + 2x + 2$ in $\mathbb{Z}_4[x] / \langle x^3 - 1 \rangle$. In order to do this, we will apply the above procedure to find a Groebner basis of the ideal $I = \langle 4, 3x^2+2x+2, x^3-1 \rangle$ of $\mathbb{Z}[x]$. We will furthermore track exactly how each element is a combination of $p_1=4, p_2=3x^2+2x+2, p_3=x^3-1$. Thus, we start with $$I = \langle 4 = p_1, 3x^2+2x+2 = p_2, x^3 - 1 = p_3 \rangle.$$ First, let us try multiplying the generator $4$ by $x^2$ to match the degree of the next generator in the list, getting $4x^2 = x^2 p_1$. Then, subtract $3x^2+2x+2$ to give $$(4x^2) - (3x^2+2x+2) = x^2-2x-2 = x^2 p_1 - p_2.$$ At this point, we cannot reduce the leading term any more, so we add this to the basis: $$I = \langle 4=p_1, x^2-2x-2=x^2 p_1-p_2, 3x^2+2x+2=p_2, x^3-1=p_3 \rangle.$$ The next move we will make will be to reduce the third element modulo the previous ones: if we take $3x^2+2x+2$ and subtract 3 times $x^2-2x-2$, we get: $$(3x^2+2x+2) - 3(x^2-2x-2) = 8x+8 = -3x^2p_1 + 4p_2.$$ Now, if we subtract $2x$ times the generator $4$, we get $8$, and again subtracting $2$ times the generator $4$, we get 0. Therefore, we can remove the third element from the basis to get: $$I = \langle 4=p_1, x^2-2x-2=x^2 p_1-p_2, x^3-1=p_3 \rangle.$$ Next, we will reduce $x^3-1$ modulo the previous elements. First, subtract $x$ times $x^2-2x-2$: $$(x^3-1) - x(x^2-2x-2) = 2x^2+2x-1 = -x^3p_1 + xp_2 + p_3.$$ Next, subtract 2 times $x^2-2x-2$: $$(2x^2+2x-1) - 2(x^2-2x-2) = 6x+3 = (-x^3-2x^2)p_1 + (x+2)p_2 + p_3.$$ Finally, subtract $x$ times the generator $4$: $$(6x+3) - x(4) = 2x+3 = (-x^3-2x^2-x)p_1 + (x+2)p_2 + p_3.$$ At this point, we cannot reduce the leading term any more, so we can replace; and after doing this replacement and resorting the list, we get: $$I = \langle 4=p_1, 2x+3=(-x^3-2x^2-x)p_1+(x+2)p_2+p_3, x^2-2x-2=x^2p_1-p_2 \rangle.$$ From here, if you multiply the generator $4$ by $x$ and then reduce modulo $2x+3$ and then modulo $4$, you get $-2 = (2x^3+4x^2+3x+1)p_1 + (-2x-4)p_2 + (-2)p_3$. Before adding to the ideal, you might as well negate, and you get: $$I = \langle 2=(-2x^3-4x^2-3x-1)p_1 + (2x+4)p_2 + 2p_3,\\4=p_1,\\2x+3=(-x^3-2x^2-x)p_1+(x+2)p_2+p_3,\\ x^2-2x-2=x^2p_1-p_2 \rangle.$$ You can now remove $4$ from the list since it is a multiple of $2$. Finally, if you reduce $2x+3$ modulo $2$, you get $$1 = (2x^4+5x^3+5x^2+3x+1)p_1 + (-2x^2-5x-2)p_2 + (-2x-1)p_3.$$ However, since $p_1$ and $p_3$ are both equivalent to 0 in $\mathbb{Z}_4[x] / \langle x^3 - 1 \rangle$, we conclude that $-2x^2-5x-2$ is the multiplicative inverse of $p_2 = 3x^2+2x+2$.

(If we had reached a point where no further moves would change the list, and neither 1 nor -1 was in the list, then this would have shown that the selected polynomial would not have been a unit in the quotient ring by the other polynomials.)

---

For information, here is a transcript of the input to Sagemath that I used to track the coefficients:

R.<x> = ZZ[]
M = R^4
p1 = R(4)
p2 = 3*x^2+2*x+2
p3 = x^3-1
B=[M((p1,1,0,0)),M((p2,0,1,0)),M((p3,0,0,1))]
B
x^2*B[0]-B[1]
B2=[B[0],_,*B[1:]]
B2
B2[2]-3*B2[1]
_-2*x*B2[0]
_-2*B2[0]
B3=[*B2[:2],*B2[3:]]
B3
B3[2]-x*B3[1]
_-2*B3[1]
_-x*B3[0]
B4=[*B3[:2],_]
B4
B5=[B4[0],B4[2],B4[1]]
B5
x*B5[0]-2*B5[1]
_+B5[0]
B6=[-_,*B5[1:]]
B6[1]-x*B6[0]
_-B6[0]
(2*x^4+5*x^3+5*x^2+3*x+1)*p1+(-2*x^2-5*x-2)*p2+(-2*x-1)*p3