- #1

- 6

- 0

if 2^n-1 is prime

prove that n is prime

prove that n is prime

- 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,820

- 0

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

- #3

- 8

- 0

I think you mean: if n^n-1 is prime where n is a whole, natural numberif 2^n-1 is prime

prove that n is prime

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

Riddhish, we understood you, no need to clarify.actually its not 2^n-1 its (2^n)-1

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

2020 Award

- 11,100

- 1,302

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

- #13

- 841

- 0

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.Well is 97513144621 prime? All of the lists I checked do not have prime numbers listed that high.

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,820

- 0

You used A = 10, B = 11, ..., Z = 35 in base 26? That's somewhat odd.Well is 97513144621 prime? All of the lists I checked do not have prime numbers listed that high.

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,051

- 18

- Last Post

- Replies
- 6

- Views
- 1K

- Last Post

- Replies
- 2

- Views
- 6K

- Last Post

- Replies
- 4

- Views
- 978

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 15

- Views
- 3K

- Replies
- 3

- Views
- 881

- Replies
- 3

- Views
- 1K

- Replies
- 5

- Views
- 3K

- Replies
- 4

- Views
- 6K

- Replies
- 1

- Views
- 14K