- #1

- 6

- 0

if 2^n-1 is prime

prove that n is prime

prove that n is prime

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter riddhish
- Start date

- #1

- 6

- 0

if 2^n-1 is prime

prove that n is prime

prove that n is prime

- #2

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

Can you factor [itex]2^{ab}-1[/itex]?

- #3

- 8

- 0

if 2^n-1 is prime

prove that n is prime

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

- #4

- 401

- 0

- #5

- 8

- 0

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.

- #6

- 695

- 2

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".2^n-1=3

(n-1)ln2=ln3

- #7

- 695

- 2

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).

- #8

- 6

- 0

actually its not 2^n-1 its (2^n)-1

- #9

- 441

- 0

actually its not 2^n-1 its (2^n)-1

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.

- #10

- 841

- 0

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.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

- 841

- 0

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.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.

- #12

mathwonk

Science Advisor

Homework Helper

- 11,312

- 1,526

it helps if you know how to factor a^n - 1.

- #13

- 841

- 0

Well is 97513144621 prime? All of the lists I checked do not have prime numbers listed that high.

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.

- #14

CRGreathouse

Science Advisor

Homework Helper

- 2,824

- 0

Well is 97513144621 prime? All of the lists I checked do not have prime numbers listed that high.

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.

- #15

- 122

- 0

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

- #16

- 403

- 1

if 2^n-1 is prime

prove that n is prime

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.

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:

- #17

- 122

- 0

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

Deacon John

- #18

Gokul43201

Staff Emeritus

Science Advisor

Gold Member

- 7,082

- 21

Share: