We consider a positive integer number and call it our modulo and denote it with $m$. We choose a positive integer number like $p$ and call it the degree of our polynomial. We select $p$ integer numbers like $a_0,a_1,\cdots,a_{p-1}$ that are relatively prime to $m$. In fact, if $Gcd$ be greatest common divisor of two numbers then I mean $$ Gcd(a_i,m)=1 \quad , \quad 0\leq i \leq p-1 \, . $$ With Maple software, I found that for every choosing of numbers $m$ and $a_i$, $0\leq i \leq p-1$, that $a_i$ be relatively prime to $m$, there is a positive integer number like $n$, that the polynomial $x^p-a_{p-1}\,x^{p-1}-a_{p-2}\, x^{p-2}-\cdots-a_1\, x-a_0$ divides the polynomial $x^n-1$ over modulo $m$. In math language, I want to say

\begin{eqnarray} \forall \, m\in \Bbb{Z^+}\quad \textit{and} \quad a_i \in \Bbb{Z}\quad, \quad 0\leq i \leq p-1 \quad \textit{where} \quad Gcd(a_i,m)=1 \Rightarrow &&\\ &&\\ \exists \, n\in \Bbb{Z^+}\quad , \quad x^p-a_{p-1}\,x^{p-1}-a_{p-2}\, x^{p-2}-\cdots-a_1\, x-a_0\mid x^n-1 \mod{m} && \end{eqnarray} For example, by choosing modulo $m=25$, and coefficients $a_i$, as follows $$ \begin{array}{ccccccc} a_0=1&,&a_1=2&,&a_2=9&,&a_3=7\\ \\ &a_4=8,&&a_5=13&,&a_6=16& \end{array} $$ with software, we found that the first number that holds in our condition is $n=3120$. It means, $$ x^7-{16}\,x^{6}-{13}\, x^{5}-{8}\, x^{4}-{7}\, x^{3}-{9}\, x^{2}-2\, x-1\mid x^{3120}-1 \mod{25} $$ Now, I have two questions. The first question is, how to prove that for every choosing modulo $m$ and coefficients $a_i$, $0\leq i \leq p-1$, where coefficients are relativity prime to modulo, there is a number like $n$, where holds in our condition. In other words, how to prove that there is a number like $n$, such that one of the factors of $x^n-1$ over modulo $m$, is the following polynomial $$ x^p-a_{p-1}\,x^{p-1}-a_{p-2}\, x^{p-2}-\cdots-a_1\, x-a_0 $$ By @Robert israel notification, the $\mathbb Z_m[X]$ is not a unique factorization domain if $m$ is composite.

My second and so important question is, when we have module and coefficients, instead of full search for finding $n$, is there an optimal and efficient algorithm for obtaining the number $n$. The mentioned condition is necessary and not sufficient. For example $$ x^4-{4}\,x^{3}- x^{2}-{2}\, x-1\mid x^{48}-1 \mod{16} $$ but the coefficients $\{1,2,1,4\}$, are not relatively prime to modulo $m=16$.

My motivation for this question is that I am working on the $n$th power of the Companion matrix over various modulo. The polynomial that I mentioned in this question is the characteristic polynomial of the companion matrix. In fact, I am studying on the order of companion matrix over different modulo. I would greatly appreciate for any suggestions

@Robert Israel companion matrix satisfies its own characteristic polynomial. Just because of this, I mentioned that the motivation of this question is related to the companion matrix and I added matrix tags. Mr Israel, I am waiting for your answer. Thank you in advance for your attention to my questions.