# 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.

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}$.

• Please see my Maple code that clarifies why i said this question is about companion matrix. – Amin235 Nov 16 '16 at 20:20
• Your answer is independent of the condition coprime. In fact, if the coefficients don't be relativity prime to modulo what problem occurs in your answer. – Amin235 Nov 16 '16 at 20:44
• If the leading coefficient is not coprime to $m$, you can't divide by $P(X)$. You need the constant coefficient coprime to $m$ to have $P(X) \mid X^{n_1} - X^{n_2}$ imply $P(X) \mid X^{n_1-n_2}-1$. – Robert Israel Nov 16 '16 at 21:54
• I appreciate your answering my question and I would be grateful if you could help me for second question. Thanks again. – Amin235 Nov 17 '16 at 10:20
• I reduced the conditions of problem to just $a_0$ be coprime to modulo $m$ and with your method we can see that the relation holds too. But it was a bit difficult to me to prove that why $P(X)$ dosnt divide $X^{n_1}$. I said, if $P(X)$ wants to divides $X^{n_1}$, then because of $a_0$ is coprime to $m$, $P(X)$ should divide $X^{n_1-1}$. But it is not true that $P(X)$ divides two consecutive power of $X$, except when $P(X)$ be power of $X$ and it is contradiction to assumption that $a_0$ is coprome to modulo $m$. Is it true discussion or not. Tanks again. – Amin235 Nov 18 '16 at 18:55