How can I show that these two polynomials are coprime?

Question

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$?

Answer 1

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\,$.

---

Answer 2

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