Author |
Topic: (2^n-1)/2 is prime (Read 549 times) |
|
cool_joh
Guest
|
Is there any solution for (2n-1)/2=q, where n is a positive integer and q is a prime number?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
Re: (2^n-1)/2 is prime
« Reply #1 on: Feb 2nd, 2008, 4:46am » |
 Quote  Modify
|
I must be missing something; if n is a positive integer, 2n is even, 2n - 1 is odd, and (2n - 1)/2 is half-integer, therefore certainly not prime...
--SMQ
|
| « Last Edit: Feb 2nd, 2008, 4:46am by SMQ » |
IP Logged |
--SMQ
|
|
|
cool_joh
Guest
|
Yeah, I also thought that there are no solutions.
|
|
IP Logged |
|
|
|
cool_joh
Guest
|
I'm sorry. The equation should be: (2n-1)/n
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: (2^n-1)/2 is prime
« Reply #4 on: Feb 3rd, 2008, 1:30am » |
Quote Modify
|
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.
|
| « Last Edit: Feb 3rd, 2008, 3:50pm by Hippo » |
IP Logged |
|
|
|
temporary
Full Member
Posts: 255
|
|
Re: (2^n-1)/2 is prime
« Reply #5 on: Feb 3rd, 2008, 9:41am » |
Quote Modify
|
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.
|
|
IP Logged |
My goal is to find what my goal is, once I find what my goal is, my goal will be complete.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: (2^n-1)/2 is prime
« Reply #6 on: Feb 3rd, 2008, 10:32am » |
Quote Modify
|
on Feb 3rd, 2008, 1:30am, 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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: (2^n-1)/2 is prime
« Reply #7 on: Feb 3rd, 2008, 11:39am » |
Quote Modify
|
on Feb 3rd, 2008, 10:32am, 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.
|
| « Last Edit: Feb 3rd, 2008, 3:58pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove