14
$\begingroup$

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

  • 5
    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$.2012-04-04
  • 0
    Generalization : http://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-12014-03-09

2 Answers 2

16

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

  • 0
    @N.S. Aren't you using recursion there? The last sentence.2016-03-05
  • 0
    @DhruvSomani The last step is just the formula $$y^q-1^q=(y-1)(y^{q-1}+..+y+1)$$2016-03-05
  • 1
    Notice that with the conditions of strict inequality in the Euclidean algorithm we cannot have dat $x^a-1$ divides $x^r-1$. So it is more precise !2017-10-16
  • 0
    I arrived that $x^{a}-1$ divides $x^{r}-1$, but how does that means $r=0$?2018-03-18
  • 0
    It seems like that $0 \le r is needed. @Maman: Is this what you meant?2018-03-18
  • 0
    @Niing He's doing the contraposite so $0 is the required condition2018-03-18
6

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.

  • 0
    Thanks for the answer, it's always interesting a more general approach2012-04-08