wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> (2^n-1)/2 is prime
        
(Message started by: cool_joh on Feb 2^nd, 2008, 2:01am)

Title: (2^n-1)/2 is prime
Post by cool_joh on Feb 2^nd, 2008, 2:01am

Is there any solution for (2ⁿ-1)/2=q, where n is a positive integer and q is a prime number?

Title: Re: (2^n-1)/2 is prime
Post by SMQ on Feb 2^nd, 2008, 4:46am

I must be missing something; if n is a positive integer, 2ⁿ is even, 2ⁿ - 1 is odd, and (2ⁿ - 1)/2 is half-integer, therefore certainly not prime...

--SMQ

Title: Re: (2^n-1)/2 is prime
Post by cool_joh on Feb 2^nd, 2008, 7:03am

Yeah, I also thought that there are no solutions.

Title: Re: (2^n-1)/2 is prime
Post by cool_joh on Feb 2^nd, 2008, 4:57pm

I'm sorry. The equation should be: (2ⁿ-1)/n

Title: Re: (2^n-1)/2 is prime
Post by Hippo on Feb 3^rd, 2008, 1:30am

Start with 2^k = 1 (mod k).

From Euler's: Let phi(k) be the number of numbers mod k which are relatively prime to k. [edit]Wrong assumption:[/edit] All are primitive phi(k)th roots of 1 (mod k).

Evidently k is odd, so k and 2 are relatively prime we know 2 is phi(k)-th primitive root mod k.
And k is multiple of phi(k).
If k is factorised as p1^e1*p2^e2*...*pi^ei we get
phi(k)=(p1-1)*p1^(e1-1)*...*(pi-1)*pi^(ei-1) so the condition means (p1-1)*(p2-1)*...*(pi-1) divides p1*p2*...*pi.

As the later is factorisation (p1-1)=1 otherwise it contain prime factor not among p1,...,pi. So p1=2, but it contradicts the asumption k is odd.

Conclusion: factorisation does not contain p1^e1 so k=1. ... But (2^1-1)/1=1 is not prime.

Title: Re: (2^n-1)/2 is prime
Post by temporary on Feb 3^rd, 2008, 9:41am

The only way to get it to even be an integer is with n=1, but then it would be 1, which is not prime nor composite. There have been some cases of 0 being positive(and of coarse it's an integer), but that would be undefined. I agree, it's impossible.

Title: Re: (2^n-1)/2 is prime
Post by Eigenray on Feb 3^rd, 2008, 10:32am

on 02/03/08 at 01:30:12, Hippo wrote:

From Euler's: Let phi(k) be the number of numbers mod k which are relatively prime to k. All are primitive phi(k)th roots of 1 (mod k).

This is not true. For example if k=7, you have elements of order 1,3,6,3,6,2. But you are on the right track.

Title: Re: (2^n-1)/2 is prime
Post by Hippo on Feb 3^rd, 2008, 11:39am

on 02/03/08 at 10:32:11, Eigenray wrote:

This is not true. For example if k=7, you have elements of order 1,3,6,3,6,2. But you are on the right track.

Ooops, I was not realy sure :(. ... I have a lot of work and made a small "refreshing" interuption ... the idea the elements are all of the same order ... especialy 1 among them :-[ ... I should take some relax ;).

BTW: I don't thing so I am on the right trackl.