Expanding 2^(ab)-1: A Guide to the Mersenne Number Theorem

[Joseph1739]

Homework Statement

I'm trying to understand a proof for Mersenne number theorem, but I'm having trouble understanding the expansion from 2^ab-1 into (2^a-1)((2^a)^b-1+(2^a)^b-2+...+2^a+1)).

Homework Equations

Not sure

The Attempt at a Solution

I don't know where to start really and I can't seem to find any proof that explains what is going on in this step.

 

[Mark44]

Homework Statement

I'm trying to understand a proof for Mersenne number theorem, but I'm having trouble understanding the expansion from 2^ab-1 into (2^a-1)((2^a)^b-1+(2^a)^b-2+...+2^a+1)).

Homework Equations

Not sure

The Attempt at a Solution

I don't know where to start really and I can't seem to find any proof that explains what is going on in this step.

They are factoring $2^{ab} - 1$ into the two factors you show. Note that $(a^m)^n = a^{mn}$.

 

[Joseph1739]

They are factoring $2^{ab} - 1$ into the two factors you show. Note that $(a^m)^n = a^{mn}$.

Sorry, I forgot to include that part. I understand that (a^m)ⁿ = a^mn. I don't see how see how (2^a)^b-1 helps with factoring this though. To be honest, before I saw this proof, I thought there were no other ways to factor it. Is there some factoring rule that I am missing?

 

[Mark44]

Sorry, I forgot to include that part. I understand that (a^m)ⁿ = a^mn. I don't see how see how (2^a)^b-1 helps with factoring this though. To be honest, before I saw this proof, I thought there were no other ways to factor it. Is there some factoring rule that I am missing?

It's not a rule that you would learn in an algebra class, I don't believe. Try it out with some specific numbers. For example, with a = 3 and b = 2, you have $2^6 - 1 = (2^3 - 1)(2^3 + 1)$.
With a = 3 and b = 3, you have $2^9 - 1 = (2^3 - 1)(2^6 + 2^3 + 1)$

 

[Joseph1739]

It's not a rule that you would learn in an algebra class, I don't believe. Try it out with some specific numbers. For example, with a = 3 and b = 2, you have $2^6 - 1 = (2^3 - 1)(2^3 + 1)$.
With a = 3 and b = 3, you have $2^9 - 1 = (2^3 - 1)(2^6 + 2^3 + 1)$

I was trying it out with (2²)³ and it simplifies to the same result. I just really wanted to know how that equivalence was derived.

 

[Dick]

I was trying it out with (2²)³ and it simplifies to the same result. I just really wanted to know how that equivalence was derived.

Look at the formula for summing a geometric series.

 

[Joseph1739]

Look at the formula for summing a geometric series.

Would that make it: ((2^ab(1-2^ab)/(1-2)) -1 = -2^2ab -1 ? Am I doing something wrong here? Ignoring the -1 right now, the first term is 2^ab, n = ab, and the common ratio is 2.

 

[Ray Vickson]

Homework Statement

I'm trying to understand a proof for Mersenne number theorem, but I'm having trouble understanding the expansion from 2^ab-1 into (2^a-1)((2^a)^b-1+(2^a)^b-2+...+2^a+1)).

Homework Equations

Not sure

The Attempt at a Solution

I don't know where to start really and I can't seem to find any proof that explains what is going on in this step.

Have you ever seen the expansion
$$x^n - 1= (x-1)(1+x+x^2+ \cdots x^{n-1})$$
for any $x$ and positive integer $n$? Just apply it to $x = 2^a$ and $n = b$, provided that $b$ is a positive integer.

 

[Joseph1739]

Have you ever seen the expansion
$$x^n - 1= (x-1)(1+x+x^2+ \cdots x^{n-1})$$
for any $x$ and positive integer $n$? Just apply it to $x = 2^a$ and $n = b$, provided that $b$ is a positive integer.

I don't know how that expansion is derived. I understand how to get expression on the right side by dividing the original polynomial by (x-1), but I don't know how (x-1) was factored with begin with.

 

[Ray Vickson]

I don't know how that expansion is derived. I understand how to get expression on the right side by dividing the original polynomial by (x-1), but I don't know how (x-1) was factored with begin with.

Sorry, I assumed everybody had seen that result before, as it is a part of elementary algebra. You can derive it from the formula for the sum
$$1 + x + x^2 + \cdots + x^k$$
Google 'geometric series'.

 

[Joseph1739]

Sorry, I assumed everybody had seen that result before, as it is a part of elementary algebra. You can derive it from the formula for the sum
$$1 + x + x^2 + \cdots + x^k$$
Google 'geometric series'.

Would't that result in = 1(1-x^k)/(1-x) = (1-x)^k-1?

 

[Ray Vickson]

Would't that result in = 1(1-x^k)/(1-x) = (1-x)^k-1?

No.

Anyway, why would you think that $(1-x^k)/(1-x) = (1-x)^{k-1}$? That is false. Try it for yourself: put $x = 1/2$ and $k = 3$ into both sides and see what happens.

Have you done what I suggested (Google 'geometric series')?

 

[epenguin]

I don't know how that expansion is derived. I understand how to get expression on the right side by dividing the original polynomial by (x-1), but I don't know how (x-1) was factored with begin with.

It looks like you know everything but don't know your know it.
You know how to get from left to right and right to left.
If the question is how did anyone hit on the fact (x - 1) is a factor of (x ⁿ - 1) without someone telling them, or the examples, they could have noticedn that x = 1 makes (x ⁿn - 1) be 0 and after a bit they said

And you should have met it in another form, see #6, though not always the relation is pointed out.

 

[Joseph1739]

Yeah, I did google geometric series. I looked at the sum of geometric series formula when the other guy posted about it. And I got:
1 = first element
x = common ratio
k = nth element

 

[Ray Vickson]

Yeah, I did google geometric series. I looked at the sum of geometric series formula when the other guy posted about it. And I got:
1 = first element
x = common ratio
k = nth element

And what formula did they give you for the finite sum?

 

[Joseph1739]

It looks like you know everything but don't know your know it.
You know how to get from left to right and right to left.
If the question is how did anyone hit on the fact (x - 1) is a factor of (x ⁿ - 1) without someone telling them, or the examples, they could have noticedn that x = 1 makes (x ⁿn - 1) be 0 and after a bit they said

That makes sense, but how does 2^a-1 factor out of (2^a)^b-1? 2 raised to a power minus 1 will not be zero anymore unless the exponent is 0.

 

[Joseph1739]

And what formula did they give you for the finite sum?

(a₁)(1-rⁿ/1-r) = (1)(1-x^k/1-x) = (1-x^k)/(1-x)

 

[epenguin]

Re #16 Just look at formula in #8 for instance.

2^a is x and b is n.b

Note that since 2^ab = (2^a)^b = (2^b)^a you can get another valid formula just exchanging a with b everywhere, there is nothing to distinguish between a and b algebraically, though extra-mathematically you might have decided on them standing for particular different things.

But maybe the question was a different one: you did not realize that nothing was being raised to power -1: the guy was just using correct notation (for a subtraction of 1 from (2^a)^b) which a lot of people don't bother with here.

 

[Mark44]

Re #16 Just look at formula in #8 for instance.

2^a is x and b is n.

Note that since 2^ab = 2^ab = 2^ba

No, these aren't right.
$2^{ab} = (2^a)^b \neq 2^{a^b}$
For example, $2^{2\cdot 3} = (2^2)^3 = 2^6 = 64$, but $2^{2^3} = 2^8 = 256$

you can get another valid formula just exchanging a with b everywhere, there is nothing to distinguish between a and b algebraically, though extra-mathematically you might have decided on them standing for particular different things.

But maybe the question was a different one: you did not realize that nothing was being raised to power -1: the guy was just using correct notation (for a subtraction) which a lot of people don't bother with here.

 

[epenguin]

Thank you typo corrected

 

[LeonhardEuler777]

Understand this:
https://www.math.iupui.edu/~ccowen/OldCoursePages/Math300F07/300F07Quiz4.pdf

My condensed version:
You know you can factor (x-1) out of (x^n-1) because x=1 is guaranteed to be a root of the polynomial (x^n-1) (because whether n is even or odd we will always get zero when x=1).

We write the second factor of our expansion so that it ends in +1. The two factors multiplied together cause a series of cancellations to occur which result in the original expression (x^n-1).

Once this is understood (as someone else mentioned already) plug in 2^ab into (x^n-1) where x=2 and n=ab.