Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $x > 1$ and $a$, $b$ be positive integers. I know that $a$ divides $b$ implies that $x^a - 1$ divides $x^b - 1$. If $b = qa$, then

$x^b - 1 = (x^a)^q - 1^q = (x^a - 1)((x^a)^{q-1} + \ldots + x^a + 1)$

I'm interested in the converse of the statement. If $x^a - 1$ divides $x^b - 1$, does this imply that $a$ divides $b$?

share|improve this question
2  
By the division algorithm, you can write $b=qa+r$ with $0 \leq r < a$. When you do long division of $x^{b} - 1$ by $x^{a} - 1$, you will eventuall encounter the remainder $x^{r} - 1$, and the process stops. If $x^{a} - 1$ divides $x^{b} - 1$, the remainder must be $0$, whence $r=0$. –  Chris Leary Apr 4 '12 at 14:57
    
Generalization : math.stackexchange.com/questions/7473/… –  lab bhattacharjee Mar 9 at 7:13
add comment

2 Answers

up vote 7 down vote accepted

Let $b=a \cdot q+r$.

Then

$$x^b-1=x^b-x^r+x^r-1=x^r(x^{aq}-1)+x^r-1 \,.$$

Use that $x^a-1$ divides $x^{aq}-1$.

share|improve this answer
    
Thanks, very simple. –  spin Apr 8 '12 at 20:02
add comment

Hint $\:$ By Theorem below $\rm\:(x^a\!-1,x^b\!-1) = x^{(a,b)}\!-1.\:$ This $\rm\: =\: x^a\!-1\!\iff\! (a,b)=a\!\iff\! a\ |\ b$

Apply Theorem to $\rm\ f_n =\ x^n\!-1\ =\ x^{n-m} \: (x^m\!-1) + x^{n-m}\!-1 =\: g\ f_m + f_{n-m}\equiv f_{n-m}\pmod{f_m}$

Theorem $\: $ If $\rm\:f_n\:$ is a sequence in a GCD domain (domain where gcds exist) satisfying $\rm\ f_{\:0} =\: 0\:\ $ and $\rm\ \: f_n\equiv f_{n-m}\ (mod\ f_m)\ $ for $\rm\: n > m\ $ then $\rm\:\ (f_n,f_m)\ =\ f_{(n,\:m)}\ \: $ where $\rm\ (i,\:j) = gcd(i,\:j)\:$.

Proof $\ $ By induction on $\rm\:n + m\:$. The theorem is trivially true if $\rm\ n = m\ $ or $\rm\ n = 0\ $ or $\rm\: m = 0\:$.
So we may assume $\rm\:n > m > 0\:$.$\ $ Note $\rm\ (f_n,f_m)\: =\ (f_{n-m},f_m)\ $ follows from the hypothesis.
Since $\rm\:\ (n-m)+m \ <\ n+m\: ,\ $ induction yields $\rm\ \ (f_{n-m},f_m)\ =\ f_{(n-m,\:m)}\ =\ f_{(n,\:m)}\ $

See this post and its links for more on such divisibility sequences.

share|improve this answer
    
Thanks for the answer, it's always interesting a more general approach –  spin Apr 8 '12 at 20:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.