Number Theory Help: Conjecture & Proof of 2^n-1 Not Prime

[chimath35]

Conjecture: suppose n is an integer larger than 1 and n is not prime. Then 2^n-1 is not prime.

Proof attached.

Could someone please explain to me how they got to xy= 2^(ab)-1. I see the -1 part. Also I think I

do not understand the concept of 2^((a-1)b) I mean is it some index or some way of showing it is

finite? I am confused.

 

[chimath35]

Okay the proof is attached, I am having a tough time understanding it.

 

[Dick]

Conjecture: suppose n is an integer larger than 1 and n is not prime. Then 2^n-1 is not prime.

Proof attached.

Could someone please explain to me how they got to xy= 2^(ab)-1. I see the -1 part. Also I think I

do not understand the concept of 2^((a-1)b) I mean is it some index or some way of showing it is

finite? I am confused.

It's just a power of 2. Try multiplying the line in question out term by term. It's what they started doing for you on the next line.

 

[chimath35]

Ya, but I don't get why only the last term has an a in it in each set of numbers?

 

[chimath35]

Also the last paragraph has me confused.

 

[chimath35]

I mean of course b has to be at least two by def. of primes but it didn't take ab = n>a to conclude that but they say it does basically. Then I get lost all after therefore.

 

[jbunniii]

Ya, but I don't get why only the last term has an a in it in each set of numbers?

The expression in the second set of parentheses on the first line is $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$. This means that there are $a$ terms being added, and the exponent of the $k$th term is $(k-1)b$.

 

[Mark44]

Could someone please explain to me how they got to xy= 2^(ab)-1. I see the -1 part. Also I think I do not understand the concept of 2^((a-1)b) I mean is it some index or some way of showing it is finite? I am confused.

(a - 1)b is the exponent on 2. Like Dick said, it's just a power of 2. Do you not understand how exponents work?

Ya, but I don't get why only the last term has an a in it in each set of numbers?

You need to be more specific. Write down the term that is confusing you.

Also the last paragraph has me confused.

What specifically is confusing in the last paragraph?

I mean of course b has to be at least two by def. of primes

No. What it says is that n is a nonprime, and a and b are both smaller than n.

but it didn't take ab = n>a to conclude that but they say it does basically. Then I get lost all after therefore.

 

[jbunniii]

I mean of course b has to be at least two by def. of primes but it didn't take ab = n>a to conclude that but they say it does basically. Then I get lost all after therefore.

Well, $b$ is not necessarily prime. But you're right, they could have simply indicated in the first sentence that we can choose $1<a<n$ and $1<b<n$ since $n$ is composite.

Since $b > 1$, we have $x = 2^b - 1 > 1$.

Since $b < n$, we have $x = 2^b - 1 < 2^n - 1$.

Together, these two facts show that $x$ is a nontrivial factor of $2^n - 1$ (i.e. $x$ is neither $1$ nor $2^n-1$), and therefore $2^n - 1$ is not prime.

[edit] fixed a couple of typos

 

[chimath35]

The expression in the second set of parentheses on the first line is $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$. This means that there are $a$ terms being added, and the exponent of the $k$th term is $(k-1)b$.

I don't get it.

 

[jbunniii]

I don't get it.

Maybe a numerical example would help. If $b = 3$ and $a = 5$ then the expression $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$ means $1 + 2^3 + 2^6 + 2^9 + 2^{12}$. Without specific numerical choices for $a$ and $b$ we have to use the $\ldots$ notation because the number of terms is a variable. In this notation, typically we write the first few terms explicitly, followed by $\ldots$, followed by the last term or two. Another way to write the same thing is
$$\sum_{k=1}^{a} 2^{(k-1)b}$$

 

[chimath35]

(a - 1)b is the exponent on 2. Like Dick said, it's just a power of 2. Do you not understand how exponents work?

I do but I don't get the a in only the last term.

You need to be more specific. Write down the term that is confusing you.

everything after therefore if you can explain

What specifically is confusing in the last paragraph?
No. What it says is that n is a nonprime, and a and b are both smaller than n.

Well, if n is not prime and a and b positive integers then a and b must be great than 2 by def. of prime. Think about it if n is composite and a and b are positive they must be atleast 2 by def. of prime. Any prime is written as 1 times itself they are the only factors.

 

[chimath35]

Maybe a numerical example would help. If $b = 3$ and $a = 5$ then the expression $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$ means $1 + 2^3 + 2^6 + 2^9 + 2^{12}$. Without specific numerical choices for $a$ and $b$ we have to use the $\ldots$ notation because the number of terms is a variable. In this notation, typically we write the first few terms explicitly, followed by $\ldots$, followed by the last term or two. Another way to write the same thing is
$$\sum_{k=1}^{a} 2^{(k-1)b}$$

Uhh thanks, I still just don't see the a-1 clearly that numerical version is simple 2^2b I don't see how or why an a is in there.

 

[jbunniii]

Uhh thanks, I still just don't see the a-1 clearly that numerical version is simple 2^2b I don't see how or why an a is in there.

The last term, $2^{12}$, is $2^{3(5-1)} = 2^{b(a-1)}$.

 

[jbunniii]

Maybe a simpler example of the notation would be helpful. What does the expression $1 + 2 + 3 + \ldots + n$ mean to you?

 

[chimath35]

So your expression means the pattern continues for n amount of numbers; also I see that x is neither 1 nor itself.

 

[chimath35]

I get it, when ever I see that expression it just means the power is going up by a certain number each time.

 

[jbunniii]

So your expression means the pattern continues for n amount of numbers

Right, and similarly for $1 + 2^b + 2^{2b} + \ldots + 2^{(a-1)b}$. The $a-1$ is telling us that the pattern continues for $a$ numbers (since the first exponent is zero).

 

[jbunniii]

I get it, when ever I see that expression it just means the power is going up by a certain number each time.

Right, the exponent increases by $b$ each time, starting at $0$ and ending at $(a-1)b$.

 

[chimath35]

Also why even write y<xy that has no meaning that I see.

 

[chimath35]

I mean I see it almost, but I am missing something...

 

[jbunniii]

Also why even write y<xy that has no meaning that I see.

Start with $x > 1$, which they showed earlier in the same sentence. Certainly I can multiply both sides by the positive number $y$ and the inequality will remain true: $xy > y$. But $xy = 2^n-1$, so this means $2^n-1 > y$.

I agree that the last paragraph seems a little obtuse. All they need to show is that $1 < x < 2^n-1$. (Then $1 < y < 2^n-1$ automatically follows.) It seems simpler to state it as I did in post 9:

Since $b > 1$, we have $x = 2^b - 1 > 1$.

Since $b < n$, we have $x = 2^b - 1 < 2^n - 1$.

Together, these two facts show that $x$ is a nontrivial factor of $2^n - 1$ (i.e. $x$ is neither $1$ nor $2^n-1$), and therefore $2^n - 1$ is not prime.

[edit] Oops, fixed a couple of typos.

 

[chimath35]

Thanks man I appreciate it, I don't know if this is because I am new to abstract math and proofs or what but I actually have to probably come back to just this one proof in a bit and/or another day to FULLY put it together. It is like my brain can only take so much of this stuff. I struggle even understanding these proofs let alone doing one right myself... I mean I can take hours sometimes "barely" getting anything done when studying this stuff. I don't know what it is or get it; maybe I am not creative, I don't know? I have gotten almost straight a's in school so far but I don't seem to grasp this kind of math.

 

[jbunniii]

No problem, mathematical proofs are hard work, and it can take a while to wrap your brain around this kind of thinking. Definitely take breaks often, you'll be less frustrated and things often seem clearer when you look at them with a fresh mind.

 

[abitslow]

The proof is really doing several different things.
The easiest to understand is that it creates two numbers, x & y which give the product
xy= (A+B+C...)- (1+A+B..) leaving you with 2ⁿ-1, all of the "middle" is subtracted away.
So to get that far you have only been given that the three integers exist such that ab=n AND that there are two integers, greater than 1 such that qr=n. Now the problem is that a and b haven't been shown to BE q and r, the positive factors of n. All that's been assumed is that their product equals n.
Here is a (flawed) counterexample showing the problem (the problem we need to show isn't valid)
if a=-1 and b = -4 then ab=4 and 2^b = 0.0625 so 2^b-1 = x = -0.9375 and that suggests that xy might not be factors (positive factors greater than 1) of 2ⁿ-1. So the rest of the proof goes on to show that x,y,a,b have the required properties to be factors >1.
You got to not just prove that given some quantities having certain properties, that the proof follows, you also have to prove that the quantities exist. "If a then b." is only a valid proof of b's existence if you can prove that a exists.

 

[chimath35]

Okay so what I just said is normal then, having to go over the proof many times to get it along with asking questions? Will the time and intensity of thinking go down considerably after a couple courses in pure math? Did you like it far less than computations when you started? I am far from giving up on this math especially before I take my proof set intro class next fall, and am working far harder on trying to get and like this pure math than I have on any other class but I REALLY enjoyed the computational math.

 

[jbunniii]

Okay so what I just said is normal then, having to go over the proof many times to get it along with asking questions?

Sure, it's very normal. You can't read math like you would read English writing. You have to go much more slowly and if it's something unfamiliar you may have to read it many times in order to understand it. Don't be reluctant to take out a pen and paper and write notes, state proofs in your own words, fill in missing gaps, etc. Studying math is a very active process.

Will the time and intensity of thinking go down considerably after a couple courses in pure math?

No. The good news is that you'll be able to read elementary proofs like this one much more quickly. As you study new things the time and mental intensity will be just as much, but you will be learning more advanced material.

Did you like it far less than computations when you started? I am far from giving up on this math especially before I take my proof set intro class next fall, and am working far harder on trying to get and like this pure math than I have on any other class but I REALLY enjoyed the computational math.

It's a different style of math compared with computation. I didn't like it much when I was first exposed to it (high school geometry I guess), but by the time I got to real analysis and abstract algebra I loved it even though it's very hard work. At the level you are studying now, the facts you are asked to prove can seem boring or pointless, but the proofs themselves are good training. Think of it as boot camp before you can move on to more interesting material. Definitely don't give up until you get a chance to study some interesting subjects - analysis, abstract algebra, topology, etc. That's where the real stuff is.