wu :: forums - Print Page


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

        riddles >> medium >> primes that differ by 1
        
(Message started by: gkwal on Jul 16^th, 2007, 9:37pm)

Title: primes that differ by 1
Post by gkwal on Jul 16^th, 2007, 9:37pm

Classify all pairs of powers of primes which differ by 1

Title: Re: primes that differ by 1
Post by towr on Jul 17^th, 2007, 1:47am

[hide]I think I read quite recently that it's only 2³,3². That, however, isn't much of a proof. [/hide]

Title: Re: primes that differ by 1
Post by Grimbal on Jul 17^th, 2007, 6:07am

2¹ and 3¹ looks ok to me.
and p⁰ and 2¹,
3¹ and 2²,
2² and 5¹.

Title: Re: primes that differ by 1
Post by towr on Jul 17^th, 2007, 6:15am

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 p^{log_p (n)}, q^{log_q (n+1)}, for p and q prime and any positive number n.

Title: Re: primes that differ by 1
Post by pex on Jul 17^th, 2007, 6:19am

on 07/17/07 at 06:07:09, Grimbal wrote:

2¹ and 3¹ looks ok to me.
and p⁰ and 2¹,
3¹ and 2²,
2² and 5¹.

Mersenne primes, anyone?

Title: Re: primes that differ by 1
Post by Grimbal on Jul 17^th, 2007, 6:20am

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 = 2ⁿ-1.

PS: as pex suggests...

Title: Re: primes that differ by 1
Post by pex on Jul 17^th, 2007, 6:44am

For higher powers, this (http://mathworld.wolfram.com/CatalansConjecture.html) is relevant.

Unrelatedly: I love the title of this thread... ;D

Title: Re: primes that differ by 1
Post by Eigenray on Aug 1^st, 2007, 6:51pm

We can give an elementary proof: Suppose p^x - q^y = 1, and that x,y > 1. Clearly either p=2 or q=2.

(I) 2^x = q^y + 1.
[hideb]Looking mod 4, we see that y must be odd. But then

2^x = (q+1)(q^y-1 - q^y-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 2^x has no odd factor.[/hideb]

(II) 2^y = p^x - 1.
[hideb]2^y = (p-1)(p^x-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

2^y = p^2z - 1 = (p^z - 1)(p^z + 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 2³ = 3² - 1.[/hideb]

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) q^y = 2^x - 1.

Then x can't be a power of q, because mod q, 2 = 2^q = 2^{q^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

q^y = 2^ab - 1 = (2^a-1)(2^a(b-1)+...+2^a+1),

and both factors are > 1, hence divisible by q. So 2^a=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 q^y = 2^p - 1 for some prime p. [Mersenne prime power]

(II) p^x = 2^y+1.

If y is not a power of 2, then we can write y = ab, where a>1 is odd. But then

p^x = (2^b+1)(2^b(a-1)-2^b(a-2) + ... - 2^b + 1),

and again both factors are > 1 hence divisible by p. But 2^b=-1 mod p implies the second factor is 1-1+...-1+1 = 1 mod p, a contradiction. So we have p^x = 2^{2^k} + 1 for some k. [Fermat prime power]