¿Cómo puedo demostrar que estos dos polinomios son coprimos?

Question

Sea $n , m \in \mathbb{N}$ y que $k = \gcd(n , m)$ . Entonces existe $p , q \in \mathbb{N}$ coprimo tal que $n = p k$ y $m = q k$ . Y es fácil ver que $$ \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{,} $$ en $X$ un indeterminado. ¿Cómo puedo demostrar que $\gcd(f(X) , g(X)) = 1$ ?

Answer 1

La siguiente es una prueba paso a paso para $k=1$ . El caso general se demuestra en mi otra respuesta a la pregunta relacionada, y los detalles se pueden rellenar de forma muy similar allí.

Se da la circunstancia de que $\,X^{p} = \left(X-1\right)f(X)+1\,$ y $X^{q} = \left(X-1\right)g(X)+1\,$ .

Desde $\,p,q\,$ son coprimos, existen enteros $\,a,b\,$ tal que $\,ap-bq=1\,$ y se puede suponer WLOG que son positivos, es decir $\,a,b \in \Bbb N\,$ (véase aquí por ejemplo). A continuación, $\,X^{ap}=X^{bq+1} = X \cdot X^{bq}\,$ y por lo tanto:

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

Por lo tanto $\,u(X) \cdot f(X) - X \cdot v(X)\cdot g(X)=X-1\,$ .

Sea $\,h(X) = \gcd\left(f(X),g(X)\right)\,$ entonces $\,h(X)\,$ divide el LHS, por lo que $\,h(X) \mid X-1\,$ . Pero..:

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

Desde $\,h(X) \mid f(X)\,$ y $\,h(X) \mid X-1\,$ se deduce que $\,h(X) \mid p = f(X)-(X-1)\cdot w(X)\,$ Así que $\,h(X)\,$ es un polinomio constante, lo que completa la prueba de que $\,\gcd(f(X),g(X))=1\,$ .

---

Answer 2

Supongamos que $m\gt n$ entonces un factor común de $x^m-1$ y $x^n-1$ deben dividir su diferencia $x^m-x^n=x^n(x^{m-n}-1)$ . En $x^n$ no puede incluir un factor común, por lo que puedes replicar el algoritmo euclidiano en los exponentes para demostrar que el factor común es $x^k-1$ .