# Arithmetic on polynomials

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

Related Calculus and Beyond Homework News on Phys.org

#### Noctisdark

Yes, It is the greatest commun divisor :)

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.

"Arithmetic on polynomials"

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving