How to prove $\,x^a-1 \mid x^b-1 \iff a\mid b$ How to prove $x^a-1\mid x^b-1 \iff a \mid b$, where $x \ge 2$ and $a,b,x \in \Bbb Z$.
I've tried the following in attempting to solve this:
$$a\mid b \Rightarrow aq=b \Rightarrow x^{aq}=x^b \Rightarrow x^ax^q=x^b$$
Because $x^q \in \Bbb Z$, it follows that $x^a\mid x^b$.
This is as far as I have gotten; any help getting further is appreciated.
Note: It may be that this identity is not true at all?
 A: It is true because $x-1$ divides $x^q - 1$ (so substitute $y=x^a$ in your calculation) in one direction. In the other direction, divide the two polynomials by long division.
A: Hint. Prove that if $0<r<a$, then $x^a-1$ does not divide $x^r-1.$ After that, make an euclidean division to get $x^{b}-1=x^{qa+r}-1$, with $0\leqslant r<a$. Now, you know that $x^b-1\equiv x^r-1\pmod{x^a-1}$. Now, prove $r=0$ and you are done.
A: This is adapted from this answer.
Since
$$
\frac{a^k-1}{a-1}=\sum_{j=0}^{k-1}a^j\tag{1}
$$
we immediately get that $x^m-1\mid x^n-1$ when $m\mid n$.
Now, suppose that $x^m-1\mid x^n-1$ and that $n=km+r$ where $0\le r< m$. Then
$$
\begin{align}
\frac{x^n-1}{x^m-1}
&=\frac{x^{km+r}-x^{km}}{x^m-1}+\frac{x^{km}-1}{x^m-1}\\
&=x^{km}\frac{x^r-1}{x^m-1}+\frac{x^{km}-1}{x^m-1}\\
&\in\mathbb{Z}\tag{2}
\end{align}
$$
It immediately follows from $(1)$ that $\frac{x^{km}-1}{x^m-1}\in\mathbb{Z}$. Therefore, we must also have $x^{km}\frac{x^r-1}{x^m-1}\in\mathbb{Z}$:
$$
x^m-1\mid x^{km}(x^r-1)\tag{3}
$$
Since $\left(x^{km},x^m-1\right)=1$, $(3)$ implies that $x^m-1\mid x^r-1$. However, since $0\le r< m$, we have that $0\le x^r-1< x^m-1$. Therefore, $x^r-1=0$; that is, $r=0$ and $n=km$; hence, $m\mid n$.
A: Hint $\rm\,\ mod\ \ x^{\large A}\!-1\!:\ \ \color{#c00}{x^{\large A}\equiv 1},\ \ \, so\ \ \ \smash[b]{\underbrace{x^{\large B}\equiv x^{\large B\ mod\ A}}} \equiv 1 \!\iff\! B\ mod\ A = 0 \!\iff\! A\mid B$
$\text{since by division}\ \  \rm B = AQ+R\,\Rightarrow\, x^{\large B}\equiv (\color{#c00}{x^{\large A }})^{\large Q} x^{\large R}\equiv {\color{#c00}1}^{\large Q} x^{\large R}\equiv x^{\large R},\ $ for $\rm\, R = B\bmod A$
The method in the above proof is called modular order reduction. It works in any ring (or monoid) since it uses only ring (or monoid) laws and consequent congruence product & power rules.

If mod  is unknown then we can instead use the Factor Theorem $\rm\,\color{#c00}z^Q-1 = (\color{#c00}z-1)q(x)$
$\ \  \rm (\color{#c00}{x^A}\!-1)q(x) = ((\color{#c00}{x^A})^Q\!-1) x^R = x^{AQ+R}\!-x^R,\ $ so $\rm\ x^{AQ+R}\!-1 = x^R\!-1 + (x^A\!-1)\, q(x)$
Remark $ $ We can show much more. The polynomial sequence $\rm\ f_n = (x^n-1)/(x-1),\, $ like the Fibonacci sequence, is a strong divisibility sequence, i.e. $\rm\: (f_m,f_n)\: =\: f_{\:(m,n)},\,$ where $\rm\,(a,b):=\gcd(a,b).\,$ The proof is simple - essentially the same as the proof of the Bezout identity for integers - see  here.  Thus we can view the polynomial Bezout identity as a q-analog of the integer Bezout identity, e.g.
$$\begin{align} \rm\ \color{#90f}3\, &=\, (\color{#0a0}{15},\ \color{#c00}{21})\\[.2em]
{\large \leadsto}\,\ \rm\ \color{#90f}{f_3}\, &=\, \rm (\color{#0a0}{f_{15}},\ \color{#c00}{f_{21}}),\, \ \text{with Bezout equation below}\\[.2em]
\color{#90f}{\frac{x^3-1}{x-1}} &= (x^{15}\! +\! x^9\! +\! 1)\ \color{#0a0}{\frac{x^{15}\!-1}{x-1}} - (x^9\!+\!x^3)\ \color{#c00}{\frac{x^{21}\!-1}{x-1}}\end{align}\ $$
For  $\rm\, x = 1\, $ it specializes to  $ \ \color{#90f}3\ =\ (3)\, \color{#0a0}{15}\, -\, (2)\, \color{#c00}{21},\, $ a Bezout equation in $\Bbb Z.\,$ It is well-worth mastering these binomial divisibility properties since they occur quite frequently in number theoretical applications and, moreover, they provide excellent motivation for the more general study of divisibility theory, $ $ esp. in divisor theory form. For an introduction see Borevich and Shafarevich: Number Theory.
A: Here's a naughty proof of the "only if" direction (Igor Rivin's proof is optimal for the other one): if $x^a - 1 \mid x^b - 1$ (where $a, b > 0$), then there is a polynomial $p(x)$ such that
$$x^b - 1 = (x^a - 1)p(x).$$
Now, $p(x)$ has a priori rational coefficients but since $x^a - 1$ is monic, by the division algorithm it in fact has integral coefficients. Differentiate both sides with respect to $x$, using the product rule:
$$b x^{b - 1} = a x^{a - 1} p(x) + (x^a - 1) p'(x).$$
Now take $x = 1$ and conclude
$$b = a \,p(1).$$
Since $p$ has integral coefficients, $p(1) \in \mathbb{Z}$ and we conclude $a \mid b$.
