# Greatest common divisor of $X^n-1$ and $X^m-1$ [duplicate]

Let $f=X^n-1$ and $g=X^m-1$ be two polynomials. Show that: $$\left(f,g\right)=X^{\left(n,m\right)}-1,$$ where $\left(a,b\right)=$ greatest common divisor of $a$ and $b$.

## marked as duplicate by Sil, lab bhattacharjee, Ross Millikan, ahulpke, SaadFeb 18 '18 at 0:16

• And what have you tried? – ajotatxe Feb 17 '18 at 14:21
• I'm supposed to use the Euclidean Division but I'm getting nowhere. – user528021 Feb 17 '18 at 14:22
• Try the standard: that is to show that $d=(x,y)$ show that $d$ divides $x$ and $y$ and that every $d'$ that divides $x$ and $y$ also dvides $d$. – ajotatxe Feb 17 '18 at 14:26
• Possible duplicate of Prove that $\gcd(a^n - 1, a^m - 1) = a^{\gcd(n, m)} - 1$ and Euclidean algorithm on $(a^n-1,a^m-1)$ – Sil Feb 17 '18 at 14:32
• Consider their roots of unity. – BAI Feb 17 '18 at 14:46

Suppose m and n have a common divisor like k such that $m=m_1k$ and $n=n_1k$ then we can write:
$x^n-1=x^{n_1k}-1=(x^k-1)(x^{n_1k-k}+x^{{n_1k-k-1}}+{x^{n_1k-k-2}}+ . . . +1)$
$x^m-1=x^{m_1k}-1=(x^k-1)(x^{m_1k-k}+x^{{m_1k-k-1}}+{x^{n_1k-k-2}}+ . . . +1)$
Which their common divisor is..$(f,g)=(x^k-1)$ or $(f,g)=x^{gcd(m,n)}-1$