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](https://en.wikipedia.org/wiki/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.



The order of companion matrix over various modulo
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}$. 


