Author |
Topic: primes that differ by 1 (Read 845 times) |
|
gkwal
Newbie
Posts: 25
|
 |
primes that differ by 1
« on: Jul 16th, 2007, 9:37pm » |
 Quote  Modify
|
Classify all pairs of powers of primes which differ by 1
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: primes that differ by 1
« Reply #1 on: Jul 17th, 2007, 1:47am » |
Quote Modify
|
I think I read quite recently that it's only 23,32. That, however, isn't much of a proof.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: primes that differ by 1
« Reply #2 on: Jul 17th, 2007, 6:07am » |
Quote Modify
|
21 and 31 looks ok to me.
and p0 and 21,
31 and 22,
22 and 51.
|
| « Last Edit: Jul 17th, 2007, 6:09am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: primes that differ by 1
« Reply #3 on: Jul 17th, 2007, 6:15am » |
Quote Modify
|
If you want to include first and zeroth powers, sure. I wouldn't call them real powers though..
And why then not go a step further and take any plog_p (n), qlog_q (n+1), for p and q prime and any positive number n.
|
| « Last Edit: Jul 17th, 2007, 6:16am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: primes that differ by 1
« Reply #4 on: Jul 17th, 2007, 6:19am » |
Quote Modify
|
on Jul 17th, 2007, 6:07am, Grimbal wrote:21 and 31 looks ok to me.
and p0 and 21,
31 and 22,
22 and 51.
|
|
Mersenne primes, anyone?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: primes that differ by 1
« Reply #5 on: Jul 17th, 2007, 6:20am » |
Quote Modify
|
AAaah, but no, there you are going to far! 
But it is true that if you accept power 1, you'll have to characterize all primes p = 2n-1.
PS: as pex suggests...
|
| « Last Edit: Jul 17th, 2007, 6:22am by Grimbal » |
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: primes that differ by 1
« Reply #6 on: Jul 17th, 2007, 6:44am » |
Quote Modify
|
For higher powers, this is relevant.
Unrelatedly: I love the title of this thread... 
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: primes that differ by 1
« Reply #7 on: Aug 1st, 2007, 6:51pm » |
Quote Modify
|
We can give an elementary proof: Suppose px - qy = 1, and that x,y > 1. Clearly either p=2 or q=2.
(I) 2x = qy + 1.
| hidden: | Looking mod 4, we see that y must be odd. But then
2x = (q+1)(qy-1 - qy-2 + ... - q + 1).
Now, q and y are odd, so the second factor is odd. But it's greater than 1, since y>1. This is a contradiciton, since 2x has no odd factor. |
(II) 2y = px - 1.
| hidden: | 2y = (p-1)(px-1 + ... + p + 1),
and the second factor must be even, since it's greater than 1. But it's congruent to x mod 2, so x is even, say x=2z, and then
2y = p2z - 1 = (pz - 1)(pz + 1).
These two factors must both be powers of 2, and they differ by 2, so they must be 2 and 4, respectively, giving the only solution 23 = 32 - 1. |
It turns out we only used the fact that one of p,q was 2, not that the other was prime.
Here was my original thought process, trying to generalize the case of Mersenne and Fermat primes:
(I) qy = 2x - 1.
Then x can't be a power of q, because mod q, 2 = 2q = 2q^2 = ..., which isn't 1 mod q. So if x is not prime, then we can write d = ab, where a,b > 1, and q doesn't divide b. But now
qy = 2ab - 1 = (2a-1)(2a(b-1)+...+2a+1),
and both factors are > 1, hence divisible by q. So 2a=1 mod q, but then the second factor = b mod q, which is not divisible by q, a contradiction. So x must be prime, and so we have qy = 2p - 1 for some prime p. [Mersenne prime power]
(II) px = 2y+1.
If y is not a power of 2, then we can write y = ab, where a>1 is odd. But then
px = (2b+1)(2b(a-1)-2b(a-2) + ... - 2b + 1),
and again both factors are > 1 hence divisible by p. But 2b=-1 mod p implies the second factor is 1-1+...-1+1 = 1 mod p, a contradiction. So we have px = 22^k + 1 for some k. [Fermat prime power]
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print