Q:

The order of companion matrix over various modulo

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.

A:

This is really about polynomials, not matrices.  Let $\mathbb Z_m$ be the ring of integers mod $m$, and $\mathbb Z_m[X]$ the polynomials over $\mathbb Z_m$ in indeterminate $X$.  Let $P(X) \in \mathbb Z_m[X]$ of degree $d$ with leading and constant terms 
coprime to $m$.  
Consider the remainders of $X^n$ on division by $P(X)$ in $\mathbb Z_m[X]$.  These are all polynomials of degree $< d$ over $\mathbb Z_m$, so there are at most $m^d$ of them.  Thus there are some $0 \le n_1 < n_2 \le m^d$ with the same remainder, i.e. $P(X)$ divides $X^{n_2} - X^{n_1}$.  But then it's easy to show that $P(X)$ divides $X^{n_2-n_1} - 1$.  Thus there is some $n \le m^d$ such that $P(X)$ divides $X^n - 1$.
Note, by the way, that it may be misleading to say "one of the factors of $x^n-1$ modulo $m$", because $\mathbb Z_m[X]$ is not a unique factorization domain if $m$ is composite.
EDIT: For finding $n$, I think it's best to use the Chinese remainder theorem.  Also note that when $m = p^e$ is a power of a prime, you can
start by finding $n$ that works for $p$ and then lift: if 
$X^n - 1$ is divisible by $P(X)$ mod $p^e$, then $X^{pn}-1$ is divisible by $P(X)$ mod $p^{e+1}$. 

