0

I have a proof and am unsure of the algebra to get from Step 2.) to Step 3.) below.

When I subtract ($2^b$ + $2^{2b}$ + $2^{3b}$ + $2^{ab}$) - (1 + $2^b$ + $2^{2b}$ + $2^{(a-1)b}$) I do the following:

Remove the ellipse and assume 4 elements in each sequence ($2^b$ + $2^{2b}$ + $2^{3b}$ + $2^{ab}$) - (1 + $2^b$ + $2^{2b}$ + $2^{(a-1)b}$)

Distribute the negative: $2^b$ + $2^{2b}$ + $2^{3b}$ + $2^{ab}$ - 1 - $2^b$ - $2^{2b}$ - $2^{(a-1)b}$

Subtract/remove opposite like terms: + $2^{3b}$ + $2^{ab}$ - 1 - $2^{(a-1)b}$

And this is as far as I could take it since I see no more like terms (same base/exponent combinations). But working backwards, I do see Step 3.) shows result $2^{ab}$ - 1 and so if I remove this I am left with: $2^{3b}$ - $2^{(a-1)b}$.

So now this implies that $2^{3b}$ - $2^{(a-1)b}$ should cancel each other out but I don't see how to do this because although they both have the same base, they don't have the same exponent.

Any help is greatly appreciated!

Theorem 3.7.1. Suppose n is an integer larger than 1 and n is not prime. Then $2^n$ - 1 is not prime. Proof. Since n is not prime, there are positive integers a and b such that a < n, b < n, and n = ab. Let x = $2^b$ - 1 and y = 1 + $2^b$ + $2^{2b}$ +· · ·+ $2^{(a-1)b}$. Then

xy = ($2^b$ - 1) · (1 + $2^b$ + $2^{2b}$ +···+$2^{(a-1)b}$)

Step 1.) = $2^b$ · (1 + $2^b$ + $2^{2b}$ +···+$2^{(a-1)b}$) - (1 + $2^b$ + $2^{2b}$ +···+$2^{(a-1)b}$)

Step 2.) = ($2^b$ + $2^{2b}$ + $2^{3b}$ +···+$2^{ab}$) - (1 + $2^b$ + $2^{2b}$ +···+ $2^{(a-1)b}$)

Step 3.) = $2^{ab}$ - 1

Step 4.) = $2^n$ - 1.

maybedave
  • 509
  • This isn't clear. Obviously $2^{3b}\neq 2^{(a-1)b}$ in general so there must be more information. What is it? – lulu Jun 12 '17 at 16:32
  • Your main issue is that you forget the "$\ldots$" in both set of parentheses. What you think is $1+2^b + 2^{2b}+2^{(a-1)b}$ is actually written as $1+2^b + 2^{2b}+\ldots+2^{(a-1)b}$, i.e. there are all the terms in between as well: $$$1+2^b + 2^{2b}+\ldots+2^{(a-1)b}= 1+2^b + 2^{2b}+2^{3b}+2^{4b}\ldots+2^{(a-2)b}+2^{(a-1)b}$$ – Clement C. Jun 12 '17 at 16:32
  • Well, for $a=5$ and $b=1$, the left hand side is $2^3=8$, but the right hand side is $2^4=16$, so it's unlikely your proof that $2^{3b}-2^{(a-1)b}=0$ is correct. – egreg Jun 12 '17 at 16:34
  • Thanks guys. This proof comes from the book "How to prove it". It is the first proof in chapter 3.7 so I would guess it is correct unless the author made a mistake but I assume he didn't – maybedave Jun 12 '17 at 16:38
  • @egreg The key is that what the OP wrote at the top, and what the proof states at the bottom, ar not the same thing. – Clement C. Jun 12 '17 at 16:38
  • @maybedave The proof is correct. The way you read it, however, is not -- you cannot "ignore" the $\ldots$ which are there to indicate there are many more terms in between. The difference is the same as if I wrote $1+2+3+\ldots+(n-1)+n$, and you read it as $1+2+3+(n-1)+n$. – Clement C. Jun 12 '17 at 16:39
  • After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark ✓ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?. – Clement C. Jun 14 '17 at 13:57

1 Answers1

0

The answer to your question is, literally, that you are right: there is no reason for which what you write should cancel to $0$: $2^{3b}-2^{(a-1)b}\neq 0$ in general.

The reason for which the proof is correct, however, is that what you did write at the top of your question misrepresents what the proof says.

Your main issue is that you forgot the "$\ldots$" in both set of parentheses. What you think is $1+2^b + 2^{2b}+2^{(a-1)b}$ is actually written as $1+2^b + 2^{2b}+\ldots+2^{(a-1)b}$, i.e. there are all the terms in between as well: $$1+2^b + 2^{2b}+\ldots+2^{(a-1)b}= 1+2^b + 2^{2b}+2^{3b}+2^{4b}\ldots+2^{(a-2)b}+2^{(a-1)b}$$

Since these terms are in both sets of parentheses, they will cancel, leaving only $2^{ab}-1$ in the end.

Clement C.
  • 67,323
  • So I removed the ellipse trying to find one case where I could perform the algebra. You highlighting this shows me that I did screw it up. If I set a = 4 to be my one case then we have

    ($2^b$ + $2^{2b}$ + $2^{3b}$ + $2^{4b}$) - (1 + $2^b$ + $2^{2b}$ + $2^{(4-1)b}$) which leaves $2^{4b}$ - 1. NOW I GET IT. THANK YOU!!!

     – maybedave Jun 12 '17 at 16:50
  • You're welcome! – Clement C. Jun 12 '17 at 16:51
  • @ Clement C. Thank you!!! – maybedave Jun 12 '17 at 16:51