Jtdylktuy

How to prove $x^a-1mid 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:

$$amid 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^amid 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?

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! Amid B$

since we have $ 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 = Bbmod A$

Remark $ $ One 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)}.,$ The proof is simple - essentially the same as the proof of the Bezout identity for integers - see my post here. Thus we can view the polynomial Bezout identity as a q-analog of the integer Bezout identity, e.g. compare the Bezout identity for the gcd $rm color{#90f}3, =, (color{#0a0}{15},,color{#c00}{21}) $ in polynomial and integer form:

$$rm 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}}$$

for $rm x = 1 $ this specializes to $ color{#90f}3 = (3) color{#0a0}{15} - (2) color{#c00}{21}., $ 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.

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.

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 $0leqslant r<a$. Now, you know that $x^b-1equiv x^r-1pmod{x^a-1}$. Now, prove $r=0$ and you are done.

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

This is adapted from this answer.

Since
$$
frac{a^k-1}{a-1}=sum_{j=0}^{k-1}a^jtag{1}
$$
we immediately get that $x^m-1mid x^n-1$ when $mmid n$.

Now, suppose that $x^m-1mid x^n-1$ and that $n=km+r$ where $0le 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}\
&inmathbb{Z}tag{2}
end{align}
$$
It immediately follows from $(1)$ that $frac{x^{km}-1}{x^m-1}inmathbb{Z}$. Therefore, we must also have $x^{km}frac{x^r-1}{x^m-1}inmathbb{Z}$:
$$
x^m-1mid x^{km}(x^r-1)tag{3}
$$

Since $left(x^{km},x^m-1right)=1$, $(3)$ implies that $x^m-1mid x^r-1$. However, since $0le r< m$, we have that $0le x^r-1< x^m-1$. Therefore, $x^r-1=0$; that is, $r=0$ and $n=km$; hence, $mmid n$.