Associated Topics || Dr. Math Home || Search Dr. Math

### 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

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search