Divisibility Proof by CasesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/