Is there a method to invert a polynomial modulo k?

Question

For instance I want to solve for $x$ the equation $$(2n+1)x\equiv 1\pmod 9$$

We can split the values of $n$ in $3$ distinct groups:

• $n=1,4,7\quad$ no solutions, since $2n+1$ is not invertible
• $n=0,3,6\quad$ gives solutions $x=1,4,7\quad$ also expressible as $\quad x\equiv n+1\pmod 9$
• $n=2,5,8\quad$ gives solutions $x=2,5,8\quad$ also expressible as $\quad x\equiv n\pmod 9$

Thus I can find and inverse for $n\mapsto 2n+1\pmod 9$ but only in a piecewise form.

I tried to gather both solutions under the form of a higher degree polynomial and found that $$x\equiv n^3+n+1\pmod 9$$

Encompasses all cases for which the original equation has solutions (i.e. for all $n\neq 1,4,7$).

I wrote a maple program to systematize this task (I limited the search to degree at most $3$)

for a from 0 to 8 do
for b from 0 to 8 do
for c from 0 to 8 do
for d from 0 to 8 do

 p:=n->2*n+1;
 q:=n->a*n^3+b*n^2+c*n+d;

 count1:=0;
 count2:=0;

 for n from 0 to 8 do

     if(gcd(p(n),9)=1) then
         count1:=count1+1;
         x:=q(n) mod 9; 
         y:=1/p(n) mod 9;
         if(x=y) then count2:=count2+1; end if:
       end if:

 end do:

 if(count1=count2) then print(sort(q('n'))); end if:

end do:
end do:
end do:
end do:

And it gave me the following possible inverses for these two examples:

$p(n)=2n+1:\begin{cases} n^3+n+1\\ n^3+3n^2+4n+1\\ n^3+6n^2+7n+1\\ n^3+6n^2+7n+1\\ 4n^3+7n+1\\ 4n^3+3n^2+n+1\\ 4n^3+6n^2+4n+1\\ 7n^3+4n+1\\ 7n^3+3n^2+7n+1\\ 7n^3+6n^2+n+1\end{cases}\qquad p(n)=3n+1:\begin{cases} 6n+1\\ 3n^3+3n+1\\ 6n^3+1\end{cases}$

Thus my question is given a polynomial $p$ can we use a systematic method to find at least one $q$ (preferably of smallest degree) such that

$$p(n)\times x\equiv 1\mod k\implies x\equiv q(n)\pmod k$$

For all values of $n$ for which the LHS has solutions ?

Note: we assume that computing $a^{-1}\pmod k$ is not an issue for integers.

Other than brute force, like I did with Maple or by interpolating for all values of $p(n)$ ?

For instance can we use Euclidian algorithm and polynomial division ?

Also $k$ is not necessarily prime, but if the prime case is (my guessing) significantly easier I'd like to know about it too.

In particular is it possible to go from the piecewise solution to the global solution applying a systematic method ?