Homework Help: A great prob

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

 

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

 

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.

 

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.

 

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

 

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.

 

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.

 

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.

 

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.

 

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

 

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.

 

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.

 

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

 

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.

 

I'll repeat my post too.

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

Deacon John

 

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.