Divisibility Proof by Cases

Date: 02/23/2003 at 11:22:48
From: Aisling
Subject: Divisibility, GCD

Prove that if d|n, then (2^d - 1)|(2^n - 1).

(Hint: x^k - 1 = (x - 1)(x^k-1 + x^k-2 +....+x^2 + x + 1))

This hint gave me no clue. What should I do?

Date: 02/23/2003 at 20:09:13
From: Doctor Greenie
Subject: Re: Divisibility, GCD

Hello, Aisling -

We are given that d|n, so n/d = a where a is an integer.

We are supposed to show that (2^d-1)|(2^n-1) - i.e., that

  (2^n-1)
  -------
  (2^d-1)

is equal to b, where b is an integer.

If we let x = 2 in the hint which is given, we have

  2^k-1 = (2-1)(2^(k-1)+2^(k-2)+ ... +2^2+2+1)

or

  2^k-1 = 2^(k-1)+2^(k-2)+ ... +2^2+2+1

So using this hint in our problem, we are supposed to show that

  2^(n-1)+2^(n-2)+ ... +2^2+2+1
  -----------------------------
  2^(d-1)+2^(d-2)+ ... +2^2+2+1

is an integer.

At first, it doesn't look as if we can show that, but we can.  Here 
are two simple example cases...:

I.  d=2, n=4

   2^4-1   2^3+2^2+2+1   (2^2)(2+1)+(2+1)   (2^2+1)(2+1)
   ----- = ----------- = ---------------- = ------------ = 2^2+1 = 5
   2^2-1       2+1             2+1              2+1

II. d=2, n=6

   2^6-1   2^5+2^4+2^3+2^2+2+1   (2^4)(2+1)+(2^2)(2+1)+(2+1)
   ----- = ------------------- = ---------------------------
   2^2-1          2+1                      2+1

   (2^4+2^2+1)(2+1)
 = ---------------- = 2^4+2^2+1 = 21
         2+1

Perhaps you can see what is going on here and can complete a formal 
proof.

I hope this helps.  Please write back if you have any further 
questions about any of this.

- Doctor Greenie, The Math Forum
  http://mathforum.org/dr.math/