• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Arithmetic on polynomials

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 ?
 
224
35
Yes, It is the greatest commun divisor :)
 
OK thank you ;-)
 
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.
 

Want to reply to this thread?

"Arithmetic on polynomials" You must log in or register to reply here.

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
Top