Homework Help: A great prob

1. May 10, 2008

riddhish

if 2^n-1 is prime
prove that n is prime

2. May 10, 2008

CRGreathouse

Can you factor $2^{ab}-1$?

3. May 10, 2008

C3H5N3O9

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. May 10, 2008

Vid

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.

5. May 10, 2008

C3H5N3O9

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. May 11, 2008

dodo

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

7. May 11, 2008

dodo

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.

8. May 12, 2008

riddhish

i m sorry

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

9. May 13, 2008

Diffy

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. May 13, 2008

ramsey2879

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 $$2^{n}-1$$ 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.

11. May 13, 2008

ramsey2879

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 $$2^{n}-1$$ 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 26, 2008

mathwonk

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

13. Jun 2, 2008

ramsey2879

A good site to obtain the factors of a number or mathematical expression such as $$2^{n} - 1$$ 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. Jun 3, 2008

CRGreathouse

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. Jun 22, 2008

DeaconJohn

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

16. Jun 23, 2008

Rogerio

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.

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: Jun 23, 2008
17. Jun 23, 2008

DeaconJohn

I'll repeat my post too.

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

Deacon John

18. Jun 23, 2008

Gokul43201

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