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

In summary, the conversation discusses a conjecture that states if n is a non-prime integer larger than 1, then 2^n-1 is also not prime. The attached proof explains how they got to the equation xy = 2^(ab)-1 and the concept of 2^((a-1)b) as a power of 2. The last paragraph explains how the proof concludes that 2^n-1 is not prime by showing that it has a nontrivial factor. The conversation also includes some confusion about the concept of 2^((a-1)b) and the reasoning behind choosing a and b as smaller than n.
  • #1
chimath35
110
0
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.
 

Attachments

  • proof 1.PNG
    proof 1.PNG
    9.9 KB · Views: 397
Physics news on Phys.org
  • #2
Okay the proof is attached, I am having a tough time understanding it.
 
  • #3
chimath35 said:
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.
 
Last edited:
  • Like
Likes 1 person
  • #4
Ya, but I don't get why only the last term has an a in it in each set of numbers?
 
  • #5
Also the last paragraph has me confused.
 
  • #6
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.
 
  • #7
chimath35 said:
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##.
 
  • Like
Likes 1 person
  • #8
chimath35 said:
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?

chimath35 said:
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.

chimath35 said:
Also the last paragraph has me confused.
What specifically is confusing in the last paragraph?
chimath35 said:
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.
chimath35 said:
but it didn't take ab = n>a to conclude that but they say it does basically. Then I get lost all after therefore.
 
  • Like
Likes 1 person
  • #9
chimath35 said:
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
 
Last edited:
  • #10
jbunniii said:
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.
 
  • #11
chimath35 said:
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}$$
 
  • Like
Likes 1 person
  • #12
Mark44 said:
(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.
 
  • #13
jbunniii said:
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.
 
  • #14
chimath35 said:
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)}##.
 
  • #15
Maybe a simpler example of the notation would be helpful. What does the expression ##1 + 2 + 3 + \ldots + n## mean to you?
 
  • #16
So your expression means the pattern continues for n amount of numbers; also I see that x is neither 1 nor itself.
 
  • #17
I get it, when ever I see that expression it just means the power is going up by a certain number each time.
 
  • #18
chimath35 said:
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).
 
  • #19
chimath35 said:
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##.
 
  • #20
Also why even write y<xy that has no meaning that I see.
 
  • #21
I mean I see it almost, but I am missing something...
 
  • #22
chimath35 said:
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.
 
  • Like
Likes 1 person
  • #23
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.
 
  • #24
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.
 
  • Like
Likes 1 person
  • #25
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.
 
  • Like
Likes 1 person
  • #26
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.
 
  • #27
chimath35 said:
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. :biggrin:
 
  • Like
Likes 1 person

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

1. What is a conjecture?

A conjecture is a statement or idea that is believed to be true but has not yet been proven.

2. What is the significance of the 2^n-1 not prime conjecture?

The 2^n-1 not prime conjecture is significant because it has important implications in number theory and the study of prime numbers.

3. How is the 2^n-1 not prime conjecture proven?

The 2^n-1 not prime conjecture is proven using mathematical proofs and techniques such as algebra, number theory, and modular arithmetic.

4. Are there any exceptions to the 2^n-1 not prime conjecture?

Yes, there are exceptions to the 2^n-1 not prime conjecture. These exceptions are known as Mersenne primes, which are numbers of the form 2^n-1 that are also prime.

5. What is the current status of the 2^n-1 not prime conjecture?

The 2^n-1 not prime conjecture has been proven for certain values of n, but it remains an open problem for larger values of n. Mathematicians continue to work on finding a general proof for all n.

Similar threads

  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
3K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
997
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
842
  • Calculus and Beyond Homework Help
Replies
3
Views
905
  • Calculus and Beyond Homework Help
Replies
15
Views
3K
Back
Top