# Homework Help: Arithmetic on polynomials

1. May 16, 2015

### geoffrey159

1. The problem statement, all variables and given/known data
What is the greatest common divisor of $X^a - 1$ and $X^b - 1$, $(a,b) \in \mathbb{N}^\star$ ?

2. Relevant equations

3. 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 ?

2. May 16, 2015

### Noctisdark

Yes, It is the greatest commun divisor :)

3. May 16, 2015

### geoffrey159

OK thank you ;-)