Author |
Topic: Prime power plus one (Read 1952 times) |
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Prime power plus one
« on: Jan 22nd, 2003, 6:36pm » |
Quote Modify
|
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.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Prime power plus one
« Reply #1 on: Jan 23rd, 2003, 7:37pm » |
Quote Modify
|
Assume the two are equal, then Since (m-1) is a factor of pn, 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 pn is zero mod p, and r is not a multiple of p which is a contradiction.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Prime power plus one
« Reply #2 on: Jan 23rd, 2003, 7:54pm » |
Quote Modify
|
That was my solution, SWF! See puzzle 39 on my puzzle site, below.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Prime power plus one
« Reply #3 on: Jan 23rd, 2003, 8:09pm » |
Quote Modify
|
on Jan 23rd, 2003, 7:37pm, 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) | pn means p | (m-1), and so (m-1)(anything) = 0 mod p.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Prime power plus one
« Reply #4 on: Jan 23rd, 2003, 8:15pm » |
Quote Modify
|
31+1 = 22 71+1 = 23 311+1 = 25 1271+1 = 27 Haven't found a solution for n != 1 yet.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Prime power plus one
« Reply #5 on: Jan 23rd, 2003, 8:17pm » |
Quote Modify
|
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>
|
« Last Edit: Jan 23rd, 2003, 8:24pm by NickH » |
IP Logged |
Nick's Mathematical Puzzles
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Prime power plus one
« Reply #6 on: Jan 26th, 2003, 9:43am » |
Quote Modify
|
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 pn=2r-1 has no solution. Obviously p can't be 2 because that would make one side odd and the other even. Since r>1, 2r is a mulitiple of 4 and 2r-1 is 3 mod 4. Since p is odd, for pn to also be 3 mod 4, n must be odd, because (2N+1)2M=(4N2+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 pn+1 term factored: 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 2r.
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Prime power plus one
« Reply #7 on: Jan 26th, 2003, 10:33am » |
Quote Modify
|
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.
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
|