How can I show that these two polynomials are coprime? 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$?
 A: 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\,$.

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