GCD of large numbers of special form I know that $\gcd(x^n-1,x^m-1) = x^{\gcd(n,m)}-1$.
What is the gcd of $x^n+1$ and $x^m+1$?
I mean, is there any method to calculate it like the one I have mentioned?
 A: The Euclidean algorithm works just as well. But if you want a formula.. First let me state a useful general theorem. The solution doesn't need the general theorem in its full strength but it helps to see the underlying structure in this kind of problems.
Theorem
For any monic polynomials $p,q$:
  $p(t) = \prod \{ (t-r) : r \in R \}$ for some multiset $R$
  $q(t) = \prod \{ (t-s) : s \in S \}$ for some multiset $S$
  Let $D = R \cap S$  [the maximum multiset that is a subset of both $R$ and $S$]
  Then $\gcd(p,q)(t) = \prod \{ (t-a) : a \in D \}$
Solution
$\gcd(x^m+1,x^n+1)$
$ = \prod \{ (x-r) : r^m+1=0 \wedge r^n+1=0 \}$ because the two polynomials have no repeated roots
$ = \prod \{ (x-e^{i2\pi t}) : t = \frac{2a+1}{2m} = \frac{2b+1}{2n} \text{ for some } a,b \in \mathbb{Z} \}$
If $m,n$ have different powers of $2$ in their factorization:
  $\frac{2a+1}{2m} \ne \frac{2b+1}{2n}$ for any integers $a,b$ and hence $\gcd(x^m+1,x^n+1) = 1$
If $m = 2^k c$ and $n = 2^k d$ for some $k \in \mathbb{Z}_{\ge 0}$ and odd $c,d$:
  Let $g = \gcd(c,d)$ and $c = eg$ and $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} \}$ because:
    $e | 2a+1$ and $f | 2b+1$
    $e,f$ are odd
  $ = \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$
