This question already has an answer here:

Let $n , m \in \mathbb{N}$ and let $k = \gcd(n , m)$. Then there exist $p , q \in \mathbb{N}$ coprime such that $n = p k$ and $m = q k$. And it is easy to see that $$ \frac{X^n - 1}{X^k - 1} = \sum_{i = 0}^{p - 1} X^{k i} = f(X) \qquad \mbox{ and } \qquad \frac{X^m - 1}{X^k - 1} = \sum_{j = 0}^{q - 1} X^{k j} = g(X)\mbox{,} $$ being $X$ an indeterminate. How can I show that $\gcd(f(X) , g(X)) = 1$?


marked as duplicate by Mike Earnest, Lord Shark the Unknown, Shailesh, Adrian Keister, mfl Aug 22 '18 at 16:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This is precisely what my answer to your other question proves. $\endgroup$ – dxiv Aug 21 '18 at 21:05
  • $\begingroup$ I have typed here that $k = \gcd(p k , q k)$. $\endgroup$ – joseabp91 Aug 21 '18 at 21:21

The following is a step-by-step proof for $k=1$. The general case is proved in my other answer to the related question, and the details can be filled-in very similarly there.

It is given that $\,X^{p} = \left(X-1\right)f(X)+1\,$ and $X^{q} = \left(X-1\right)g(X)+1\,$.

Since $\,p,q\,$ are coprime, there exist integers $\,a,b\,$ such that $\,ap-bq=1\,$, and it can be assumed WLOG that they are positive i.e. $\,a,b \in \Bbb N\,$ (see here for example). Then $\,X^{ap}=X^{bq+1} = X \cdot X^{bq}\,$, and therefore:

$$ \begin{align} 0 &= \left(\left(X-1\right)f(X)+1\right)^{a} - X \cdot \left( \left(X-1\right)g(X)+1\right)^b \\[5px] &= \Big(\underbrace{(X-1)^af^a(X)+ \binom{a}{1}(X-1)^{a-1}f^{a-1}(X)+\ldots+\binom{a}{a-1}(X-1)f(X)}_{u(X) \cdot f(X)}+1\Big) \\ &\quad - X \cdot \Big(\underbrace{(X-1)^bg^b(X)+ \binom{b}{1}(X-1)^{b-1}g^{b-1}(X)+\ldots+\binom{b}{b-1}(X-1)g(X)}_{v(X) \cdot g(X)}+1\Big) \\[5px] &= u(X) \cdot f(X) - X \cdot v(X)\cdot g(X) + 1 - X \end{align} $$

Therefore $\,u(X) \cdot f(X) - X \cdot v(X)\cdot g(X)=X-1\,$.

Let $\,h(X) = \gcd\left(f(X),g(X)\right)\,$, then $\,h(X)\,$ divides the LHS, so $\,h(X) \mid X-1\,$. But:

$$ \begin{align} f(X) &= 1 + X + X^2 + \ldots+X^{p-1} \\ &= p + (X-1)+(X^2-1)+\ldots+(X^{p-1}-1) \\ &= p+\underbrace{(X-1)+(X-1)(X+1)+\ldots+(X-1)(X^{p-2}+X^{p-3}+\ldots+1)}_{(X-1) \cdot w(X)} \\ &= p + (X-1) \cdot w(X) \end{align} $$

Since $\,h(X) \mid f(X)\,$ and $\,h(X) \mid X-1\,$ it follows that $\,h(X) \mid p = f(X)-(X-1)\cdot w(X)\,$, so $\,h(X)\,$ is a constant polynomial, which completes the proof that $\,\gcd(f(X),g(X))=1\,$.

  • $\begingroup$ It looks very worked. I have to admit. What is LHS? $\endgroup$ – joseabp91 Aug 21 '18 at 22:07
  • $\begingroup$ @joseabp91 LHS is an acronym for "left hand side" (of an equation, usually). Here, the LHS is the red part in $\,\color{red}{u(X) \cdot f(X) - X \cdot v(X)\cdot g(X)}=X-1\,$. $\endgroup$ – dxiv Aug 21 '18 at 22:09
  • 1
    $\begingroup$ Thank you very much. I have to recognize that your answer is very worked. Your input is very useful. $\endgroup$ – joseabp91 Aug 21 '18 at 22:23

Suppose $m\gt n$ then a common factor of $x^m-1$ and $x^n-1$ must divide their difference $x^m-x^n=x^n(x^{m-n}-1)$. The $x^n$ piece can't include a common factor, so you can replicate the Euclidean algorithm on the exponents to show that the common factor is $x^k-1$.

  • $\begingroup$ Do you mean that if $p(x)$ is a common factor of $x^m - 1$ and $x^n - 1$, then $p(x)$ cannot divide to $x^n$? $\endgroup$ – joseabp91 Aug 21 '18 at 21:27
  • $\begingroup$ I mean no power of $x$ can be a factor of a common factor, because $x$ does not divide either of the original polynomials. $\endgroup$ – Mark Bennet Aug 21 '18 at 21:42

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