$ \gcd(x^n-1,x^m-1)=x^d-1$ Show $$ \gcd(x^n-1,x^m-1)=x^d-1$$

Trying Euclidian Algorithm where $n=mq+r$
$$ x^n-1=x^m-1 q(x)+x^{r}-1$$
Now 
$$\begin{aligned}
 \gcd(x^n-1,x^m-1)&=gcd(x^n-1,x^r-1)
                   \\&= \vdots
                   \\&= x^d-1
\end{aligned}$$

Trying out with basic defitions
GCD polynomials $\in F[x]$
$\forall f,h \in F[x]$ ,where ($f\neq 0 \vee g\neq 0$)
$\exists $(unique) $d\in F[x]$
s.t.  


*

*$d|f\wedge d|h$

*$d$ is monic

*$d$ has maximal degree and $d|f\wedge d|h$

Def Euclidean Domain $gcd$
Let $R$ be a Euclidean domain  
$\forall a,b \in R$ where at leats one is not zero
,$\exists d \in R$ s.t 


*

*$d|a \wedge d |b$

*$c|a,c|b \Rightarrow \delta(c) \leq \delta (d)$


Guessing $\delta$ is somekind of  norm  
Def gcd Integers
$\forall a,b \in Z$ both not zero, $\exists d\in Z$ s.t


*

*$d|a \wedge d|b$

*$c|a\wedge c|b \Rightarrow c\leq d$



Using basic tools 
does $d|n$ so $n=k_1 d $ ,$\exists k_1 \in Z$ s.t
$$\begin{aligned}
x^n-1&=(x^d-1)(x^{k_1}+1)=x^{d+k_1}-1
\end{aligned} $$ 

More tools
Thm 1.2 Hungerford
$\forall a,b \in Z$ (not both 0) \exists u,v\in Z (not necassary unique)$
s.t. $$ d=nu+mv$$
Thm for polynomials
$\forall f(x),h(x) \in F[x] , \exists u(x),v(x) \in F[x]$
s.t. $$ d(x)=f(x)u(x)+g(x)v(x)$$

Trying an example to see somekind of a pattern and then try to work an argument in genal
considering $x^6-1$ and $x^2-1$
$$ x^6-1=(x^2-1)(x^4+x^2+x)+0$$
the $gcd(6,2)=2$ so the gcd in polynomials is 
$ x^6-1=(x^2-1)(x^4+x^2+1)+0$
 A: You can use induction on $\max\{m,n\}$. Let $m\ge n$.
If $m=1$ the requested is obvious. Let's assume that it is true for values $<m$. The requested is also obvious when $m=n$, so we can assume that $m>n$. Then $m=nq+r$
with $q,r\in\mathbb{Z_{>0}}$ and $0\leq r<n$. Then we know that gcd$(n,r)$=gcd$(m,n)=d$. Now we have: $$x^m-1=x^{nq+r}-1=x^rx^{nq}-x^r+x^r-1=x^r(x^{nq}-1)+x^r-1=x^rq(x)(x^n-1)+x^r-1.$$
So $\gcd(x^m-1,x^n-1)=\gcd(x^n-1,x^r-1)=x^{\gcd(n,r)}-1=x^d-1$.
A: We have:
$$x^m-1=\prod_{k=1}^{m}\left(x-e^{\frac{\pi i k}m}\right)$$
$$x^n-1=\prod_{k=1}^{n}\left(x-e^{\frac{\pi i k}n}\right)$$
Since all those factors are prime in $\mathbb{C}[X]$ and $\mathbb{C}[X]$ is a UFD, $\gcd(x^m-1,x^n-1)$ is equal to the product of the common factors, aka factors
$$\left(x-e^{\frac{i\pi k}m}\right)$$
for which there is an $1\le l\le n$ with:
$$e^{\frac{\pi i l}n}=e^{\frac{\pi i k}m}\implies \frac ln=\frac km$$
looking at those fractions in their lowest terms, both must have equal denominators and that denominator must divide both $m$ and $n$. So if we let $d=\gcd(n,m)$, then that fraction must be $j/d$ for some $j$. Therefore:
$$\gcd(x^m-1,x^n-1)\mid\prod_{k=1}^{d}\left(x-e^{\frac{\pi i k}d}\right)=x^d-1$$
Now, write $n=dn'$ and $m=dm'$. Since
$$x^n-1=(x^d-1)\sum_{k=0}^{n'}x^k$$
$$x^m-1=(x^d-1)\sum_{k=0}^{m'}x^k$$
it follows that $x^d-1\mid \gcd(x^n-1,x^m-1)$ and we conclude:
$$\gcd(x^n-1,x^m-1)=x^d-1$$
