Yo sé eso $\gcd(x^n-1,x^m-1) = x^{\gcd(n,m)}-1$.
¿Qué es el gcd de$x^n+1$ y$x^m+1$?
Quiero decir, ¿hay algún método para calcularlo como el que he mencionado?
Respuesta
¿Demasiados anuncios?
El algoritmo de Euclides funciona igual de bien. Pero si quieres una fórmula.. en Primer lugar, permítanme un estado general útil teorema. La solución no necesita el teorema general en toda su fuerza, pero ayuda a ver la estructura subyacente en este tipo de problemas.
Teorema de
Para cualquier monic polinomios $p,q$:
$p(t) = \prod \{ (t-r) : r \in R \}$ para un conjunto múltiple $R$
$q(t) = \prod \{ (t-s) : s \in S \}$ para un conjunto múltiple $S$
Deje $D = R \cap S$ [el máximo conjunto múltiple, que es un subconjunto de ambos $R$$S$]
A continuación, $\gcd(p,q)(t) = \prod \{ (t-a) : a \in D \}$
Solución
$\gcd(x^m+1,x^n+1)$
$ = \prod \{ (x-r) : r^m+1=0 \wedge r^n+1=0 \}$ debido a que los dos polinomios no tienen raíces repetidas
$ = \prod \{ (x-e^{i2\pi t}) : t = \frac{2a+1}{2m} = \frac{2b+1}{2n} \text{ for some } a,b \in \mathbb{Z} \}$
Si $m,n$ tienen diferentes poderes de $2$ en su factorización:
$\frac{2a+1}{2m} \ne \frac{2b+1}{2n}$ para cualquier enteros $a,b$ y, por tanto, $\gcd(x^m+1,x^n+1) = 1$
Si $m = 2^k c$ $n = 2^k d$ algunos $k \in \mathbb{Z}_{\ge 0}$ e impares $c,d$:
Deje $g = \gcd(c,d)$ $c = eg$ $d = fg$
$\gcd(x^m+1,x^n+1)$
$ = \prod \{ (x-e^{i2\pi t}) : 2^k t = \frac{(2a+1)f}{2efg} = \frac{(2b+1)e}{2efg} \text{ for some } a,b \in \mathbb{Z} \}$
$ = \prod \{ (x-e^{i2\pi t}) : 2^k t = \frac{(2a'+1)ef}{2efg} = \frac{(2b'+1)ef}{2efg} \text{ for some } a',b' \in \mathbb{Z} \}$ porque:
$e | 2a+1$ $f | 2b+1$
$e,f$ son impares
$ = \prod \{ (x-e^{i2\pi t}) : 2^k t = \frac{2j+1}{2g} \text{ for some } j \in \mathbb{Z} \}$
$ = \prod \{ (x-e^{i2\pi t}) : t = \frac{2j+1}{2(2^kg)} \text{ for some } j \in \mathbb{Z} \}$
$ = x^{2^kg}+1$
