What is the Greatest Common Divisor of Two Polynomials?

[geoffrey159]

Homework Statement

What is the greatest common divisor of $X^a - 1$ and $X^b - 1$, $(a,b) \in \mathbb{N}^\star$ ?

Homework Equations

The Attempt at a Solution

Assuming that $a\le b$, I find by euclidian division of $b$ by $a$ that

$b = an + r \Rightarrow X^b - 1 = (X^a-1) (\sum_{k=1}^{n} X ^ {b-ka}) + X ^r - 1$

So $\text{gcd}(X^b - 1,X^a - 1) = \text{gcd}(X^a - 1,X^r - 1)$
So if I apply Euclid's algorithm on $a$ and $b$, I will automatically get that the last non-zero remainder, which is $\text{gcd}(a,b)$, guarantees that $X ^{ \text{gcd}(a,b) } - 1$ is the last non-zero remainder of the algorithm applied on $X^a - 1$ and $X^b - 1$, and therefore is their greatest common divisor. Right ?

 

[Noctisdark]

Yes, It is the greatest commun divisor :)

 

[geoffrey159]

OK thank you ;-)

 

[Michael Hardy]

So $\text{gcd}(X^b - 1,X^a - 1) = \text{gcd}(X^a - 1,X^r - 1)$

In MathJax and LaTeX, don't write \text{gcd}; instead write \gcd. Unlike \text{gcd} this will yield proper spacing in expressions like $8\gcd(a,b)$, whereas with \text{gcd} you'll see $8\text{gcd}(a,b)$ instead, with the conspicuous lack of spacing. And the amount of space to the left and right of $\gcd$ will actually depend on the context.