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?

Solution 1:

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.

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 Borovich and Shafarevich: Number Theory.

Solution 2:

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.

Solution 3:

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.

Solution 4:

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$.