This question already has an answer here:

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, Saad Feb 18 '18 at 0:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ And what have you tried? $\endgroup$ – ajotatxe Feb 17 '18 at 14:21
  • $\begingroup$ I'm supposed to use the Euclidean Division but I'm getting nowhere. $\endgroup$ – user528021 Feb 17 '18 at 14:22
  • $\begingroup$ 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$. $\endgroup$ – ajotatxe Feb 17 '18 at 14:26
  • 4
    $\begingroup$ 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)$ $\endgroup$ – Sil Feb 17 '18 at 14:32
  • $\begingroup$ Consider their roots of unity. $\endgroup$ – 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$


Not the answer you're looking for? Browse other questions tagged or ask your own question.