wu :: forums - Print Page


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

        riddles >> easy >> Prime power plus one
        
(Message started by: NickH on Jan 22^nd, 2003, 6:36pm)

Title: Prime power plus one
Post by NickH on Jan 22^nd, 2003, 6:36pm

Show that p^n + 1 = m^r,

where p > 1 is prime, and r > 1 is not a multiple of p,

has no solution for n, m in positive integers.

Title: Re: Prime power plus one
Post by SWF on Jan 23^rd, 2003, 7:37pm

Assume the two are equal, then

http://tcw2.ppsw.rug.nl/~towr/PHP/formula.php?formula=p^n=m^r-1=(m-1)\sum_{k=0}^{r-1}m^k

Since (m-1) is a factor of pⁿ, it must be that: m=1 mod p. That means each term in the summation is 1 mod p, so the summation is r mod p, and therefore so is (m-1) times the summation. But pⁿ is zero mod p, and r is not a multiple of p which is a contradiction.

Title: Re: Prime power plus one
Post by NickH on Jan 23^rd, 2003, 7:54pm

That was my solution, SWF!

See puzzle 39 on my puzzle site, below.

Title: Re: Prime power plus one
Post by Icarus on Jan 23^rd, 2003, 8:09pm

on 01/23/03 at 19:37:23, SWF wrote:

so the summation is r mod p, and therefore so is (m-1) times the summation.

I don't follow this. Yes the sum = r mod p, but how do you get from there to (m-1)[sum] = r mod p ?

Unless m = 2, (m-1) | pⁿ means p | (m-1), and so (m-1)(anything) = 0 mod p.

Title: Re: Prime power plus one
Post by Icarus on Jan 23^rd, 2003, 8:15pm

3¹+1 = 2²
7¹+1 = 2³
31¹+1 = 2⁵
127¹+1 = 2⁷

Haven't found a solution for n != 1 yet.

Title: Re: Prime power plus one
Post by NickH on Jan 23^rd, 2003, 8:17pm

Since p is a prime, both factors must be powers of p.

You're right -- SWF didn't explicitly state that in his proof.

<edit>
Thanks! I forgot to specify n,m > 1.
</edit>

Title: Re: Prime power plus one
Post by SWF on Jan 26^th, 2003, 9:43am

Yes, that "proof" was quite reckless, and and I will try to salvage something from it. The (m-1) term in the factored expression must equal either 1 or be a multiple of p. If it is a multiple of p, the sum equals either r mod p or 1. The sum can't be one since r>1. The sum must also be a multiple of p which is a contradiction.

A more serious omission from the proof, which is also missing from the proof on NickH's web site, is the case when m-1=1; m=2. In this case, m is not 1 mod p and the sum is not necessarily r mod p. It still remains to show that pⁿ=2^r-1 has no solution. Obviously p can't be 2 because that would make one side odd and the other even. Since r>1, 2^r is a mulitiple of 4 and 2^r-1 is 3 mod 4. Since p is odd, for pⁿ to also be 3 mod 4, n must be odd, because (2N+1)^2M=(4N²+4N+1)^M=1 mod 4.

With n determined to be odd, the 1 in the assumed equality can be moved back to the left side and the pⁿ+1 term factored:

http://tcw2.ppsw.rug.nl/~towr/PHP/formula.php?formula=p^n%2B1=2^r=(p%2B1)\sum^{n-1}_{k=0}(-p)^k

The summation has an odd number of odd terms, so it is odd. It is also greater than 1. This is not possible because it needs to be a factor of 2^r.

Title: Re: Prime power plus one
Post by NickH on Jan 26^th, 2003, 10:33am

Oops -- thank you for pointing that out, SWF! I have temporarily excluded the case m = 2 on my site, until I can update the proof.