- 535

- 71

**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 ?