Finding modular inverse of a polynomial

Question

With reference to this article, I'm curious about how the modular inverse of a polynomial is computed. Moudluar inverse of a number with respect to a modulus exists when the two numbers are relatively prime. I was initially expecting this to hold for coefficients of a polynomial function.

Answer 1

Here they can mean two thing by mod n:

• The extension of the quotient $0 \to n \mathbb{Z} \to \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z} \to 0$ to $\mathbb{Z}[X]$ (polynomial with integer coefficients), which is the quotient $$0 \to n \mathbb{Z}[X] \to \mathbb{Z}[X] \to \mathbb{Z}[X]/n\mathbb{Z}[X] = (\mathbb{Z}/n \mathbb{Z})[X] \to 0$$ This means you consider only polynomials with modular coefficients. However this is very unlikely, the second possibility should be the correct one. In this case, invertible elements are complicated to describe.
• The quotient by the ideal $(X^n)$, which means you truncate every polynomial to degree $n$, i.e, if you have the polynomial $f = a_0 + \dots + a_{n-1} X^{n-1} + \dots + a_m X^m$, the class $[f]$ of $f$ in $A[X]/ (X^n)$ (with $A$ your base ring, e.g. $A = \mathbb{R}, \mathbb{Z},\dots$) will be $$[f] = a_0 + \dots + a_{n-1} X^{n-1}$$

I'll consider we work in the second configuration. To find the inverse, you need to have a polynomial that is coprime with $X^n$, i.e. it doesn't admit $0$ as a root, i.e. $a_0 \neq 0$. It is also reasonable to suppose that $A$ is a field $k$. You then need to find the bézout coefficient, you can use intuition or extended Euclide's algorithm, you then have $$af + bX^n = 1 $$ Then look at this equality "mod n" as they say (it's more mod $X^n$ in reality), you get $$[1] = [a] [f] + [b] [X^n] = [a] [f]$$ thus your modular inverse is $[a]$.

Here is an example for $n = 2$ and $f = X+1$, you have $(1-X) f + X^2 = 1$, so your modular inverse mod 2 is $(X-1)$.