$x^a - 1$ divides $x^b - 1$ if and only if $a$ divides $b$ 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$?
 A: Hint $\:$ By Theorem below  $\rm\:(x^a\!-1,x^b\!-1) = x^{(a,b)}\!-1$ $[ \rm\: =\: x^a\!-1\!\iff\! (a,b)=a\!\iff\! a\mid b\,]$
when applied 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.
A: Let $b=a \cdot q+r$, where $0 < r < a$.
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$.
