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

  • $\begingroup$ Please see my Maple code that clarifies why i said this question is about companion matrix. $\endgroup$ – Amin235 Nov 16 '16 at 20:20
  • $\begingroup$ 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. $\endgroup$ – Amin235 Nov 16 '16 at 20:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – Robert Israel Nov 16 '16 at 21:54
  • $\begingroup$ I appreciate your answering my question and I would be grateful if you could help me for second question. Thanks again. $\endgroup$ – Amin235 Nov 17 '16 at 10:20
  • $\begingroup$ 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. $\endgroup$ – Amin235 Nov 18 '16 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.