1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory help

  1. Mar 13, 2014 #1
    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.
     

    Attached Files:

  2. jcsd
  3. Mar 13, 2014 #2
    Okay the proof is attached, I am having a tough time understanding it.
     
  4. Mar 13, 2014 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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: Mar 13, 2014
  5. Mar 13, 2014 #4
    Ya, but I don't get why only the last term has an a in it in each set of numbers?
     
  6. Mar 13, 2014 #5
    Also the last paragraph has me confused.
     
  7. Mar 13, 2014 #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.
     
  8. Mar 14, 2014 #7

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##.
     
  9. Mar 14, 2014 #8

    Mark44

    Staff: Mentor

    (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?

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

    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.
     
  10. Mar 14, 2014 #9

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Mar 14, 2014
  11. Mar 14, 2014 #10
    I don't get it.
     
  12. Mar 14, 2014 #11

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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}$$
     
  13. Mar 14, 2014 #12
    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.
     
  14. Mar 14, 2014 #13
    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.
     
  15. Mar 14, 2014 #14

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The last term, ##2^{12}##, is ##2^{3(5-1)} = 2^{b(a-1)}##.
     
  16. Mar 14, 2014 #15

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Maybe a simpler example of the notation would be helpful. What does the expression ##1 + 2 + 3 + \ldots + n## mean to you?
     
  17. Mar 14, 2014 #16
    So your expression means the pattern continues for n amount of numbers; also I see that x is neither 1 nor itself.
     
  18. Mar 14, 2014 #17
    I get it, when ever I see that expression it just means the power is going up by a certain number each time.
     
  19. Mar 14, 2014 #18

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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).
     
  20. Mar 14, 2014 #19

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Right, the exponent increases by ##b## each time, starting at ##0## and ending at ##(a-1)b##.
     
  21. Mar 14, 2014 #20
    Also why even write y<xy that has no meaning that I see.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Number theory help
  1. Number theory help (Replies: 1)

  2. Number theory help (Replies: 4)

  3. Number Theory Help (Replies: 40)

  4. Number theory help (Replies: 3)

Loading...