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!

A great prob

  1. May 10, 2008 #1
    if 2^n-1 is prime
    prove that n is prime
     
  2. jcsd
  3. May 10, 2008 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Can you factor [itex]2^{ab}-1[/itex]?
     
  4. May 10, 2008 #3
    I think you mean: if n^n-1 is prime where n is a whole, natural number
    prove that n is prime.

    Otherwise you can do:
    2^n-1=3 (as 3 is a prime number number)
    (n-1)ln2=ln3
    n-1=(ln3)/(ln2)
    n=2.58496....
    Thus n is not necessarily a prime number.

    If n has to be a whole, natural number then yes, n is prime

    This is because 2^any natural, whole number equals an even number

    and the only even number that is prime is 2; thus n would have to equal 2 as 2^2-1=2
     
  5. May 10, 2008 #4

    Vid

    User Avatar

    The idea behind this problem is not setting 2^(n) - 1 (not 2^(n-1) like you have) equal to a prime in solving for n, (in virtually every problem in number theory n is limited to the natural numbers so for most cases this is an exercise in futility). The point here is, for example, 2^3 - 1 = 7 thus 3 is prime.
     
  6. May 10, 2008 #5
    If n is not limited to natural numbers then I showed that if 2^n-1 is prime, n is not necessarily prime.
    I also showed that if n was limited to natural numbers and 2^n-1 is prime, then n would indeed have to be prime.
     
  7. May 11, 2008 #6
    Read again. When doing this step,
    you interpreted 2^n-1 as "2 raised to the (n-1) power". The ordinary precedence (and what everybody else has understood the problem was) asks you to interpret it as "2^n, and then subtract 1".
     
  8. May 11, 2008 #7
    Besides, CRGreathouse already gave a solution.

    If n is composite = ab, where a,b are both > 1, then 2^ab-1 can be decomposed as the product of the following two binary numbers:
    • 2^a-1 (in binary, 11111... with 'a' ones), and
    • 1...00001...00001...00001 (that is, ...00001 repeated 'b' times, where each '...00001' contains 'a' digits in total, namely (a-1) zeroes plus 1 one).
    When you multiply both, you obtain 'ab' ones, which is 2^ab-1; thus 2^ab-1 is composite. It follows that, if 2^n-1 is prime, n must be prime.
     
  9. May 12, 2008 #8
    i m sorry

    actually its not 2^n-1 its (2^n)-1
     
  10. May 13, 2008 #9
    Riddhish, we understood you, no need to clarify.

    As Dodo said, most people would take 2^n -1 to be (2^n) - 1, I am not sure why C3H5N3O9 thought otherwise.
     
  11. May 13, 2008 #10
    C3H5N3O9 points out that if n is not a natural number it is not prime. For instance there is an irrational number n such that [tex]2^{n}-1[/tex] is equal to 13 which is prime but since n is irrational, it cant be prime. I dont know why C3H5N309 used the example of 3 and the logic there is not correct but the idea that one must specify that n is a natrual number is correct. Usually one write n to signify an integer an not an irrational number so the original poster obviously meant n to be an integer, but C3H5N309 apparently wants more care taken to specify what is meant.
     
  12. May 13, 2008 #11
    C3H5N3O9 points out that if n is not a natural number it is not prime. For instance there is an irrational number n such that [tex]2^{n}-1[/tex] is equal to 13 which is prime but since n is irrational, it cant be prime. I dont know why C3H5N309 used the example of 3 and the logic there is not correct but the idea that one must specify that n is a natrual number is correct. Usually one write n to signify an integer an not an irrational number so the original poster obviously meant n to be an integer, but C3H5N309 apparently wants more care taken to specify what is meant.
     
  13. May 26, 2008 #12

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    it helps if you know how to factor a^n - 1.
     
  14. Jun 2, 2008 #13
    A good site to obtain the factors of a number or mathematical expression such as [tex]2^{n} - 1[/tex] is http://www.alpertron.com.ar/ECM.HTM It does very well even with "large" numbers.

    There was another site that gave a "listing of all primes" up to about twice as many as up through 20940343. But the site moved or is no longer up. I know because I downloaded a good portion, the first 35 of some 80 blocks of 50,001 primes each of the listing but later I found my listing skipped a large block of consecutive primes. The listing was in 35 blocks of 50,000 primes and I am quite certain that the last prime listed in the 35th block, 20940343, should have been somewhere in the middle of the 36th block of primes. One prime was found missing and by comparing the density of the primes and the size of gap where the prime was missing I figured that about several thousand primes were obviously missing from the list.
     
  15. Jun 3, 2008 #14

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    You used A = 10, B = 11, ..., Z = 35 in base 26? That's somewhat odd.

    Using base 36 I get 684621684561, which is semiperfect (divisible by 3, in this case). Using base 26 and A = 0, B = 1, ..., Z = 25 I get another semiperfect, 17076053081 = 64153 * 266177.
     
  16. Jun 22, 2008 #15
    Riddish,
    Isn't 2^n - 1 a Mersenne number?
    If so, perhaps C3H5H309's 97513144621 could be found in one of the many lists that that tell which Merseene numbers are prime.
    DeaconJohn
     
  17. Jun 23, 2008 #16

    Suppose n is not prime.

    Then, n = p*q , p and q integers > 1

    So, 2^n-1 = 2^(p*q) - 1 =

    [2^q - 1] * [2^(0*q) + 2^(1*q) + 2^(2*q) +...+ 2^((p-1)*q)] , which is not prime.

    -> CONTRADICTION !

    So, n is prime.

    :smile:


    PS: I had already post this, but when someone moved this thread (from number theory to homework questions), all the second page was deleted.
     
    Last edited: Jun 23, 2008
  18. Jun 23, 2008 #17
    I'll repeat my post too.

    Thank you Rogerio. I had forgotten that argument. It is good to be reminded.

    Deacon John
     
  19. Jun 23, 2008 #18

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Please note that posting complete solutions to standard textbook problems is in violation of the forum guidelines. If you haven't read the guidelines in a while, please find them by clicking "Rules" in the top forum toolbar or the link in my signature line.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A great prob
  1. LaPlace Probs! (Replies: 8)

  2. Prob. on function (Replies: 6)

  3. Taylor prob (Replies: 2)

  4. Probs and stats (Replies: 1)

  5. Finding A. Prob. (Replies: 14)

Loading...