Author |
Topic: Primes (Read 780 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
a) Prove that, if 2n + 1 is a prime, then n is a power of 2.
b) Prove that, for positive integers a, n with n > 1, if an - 1 is prime, then a = 2 and n is prime.
|
| « Last Edit: Nov 7th, 2002, 8:48am by Pietro K.C. » |
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
 |
Re: NEW PROBLEM: PRIMES
« Reply #1 on: Oct 16th, 2002, 1:04am » |
 Quote  Modify
|
(b) is a quickie. I think I've seen a proof for (a) but can't remember it offhand.
Hint for (b):
Think of writing an-1 in base a. What does it look like?
Solution for (b):
(an - 1) = (a - 1) (an-1 + ... + a + 1),
which is divisible by a - 1 and hence composite if a > 2.
If a=2 and n = ij, we can split the sum on the right into i groups of j terms and factor it as
(aj-1 + aj-2 + ... + 1) * (an-j + an-2j + ... + 1)
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PROBLEM: PRIMES
« Reply #2 on: Oct 16th, 2002, 7:39am » |
Quote Modify
|
Yeah, if you go about it the right way, it's really easy. I posted this one to attract more people to the Putnam forum... doesn't appear to have worked, does it? 
Anyway, good job on the second solution to (b)! I'd never seen it done that way before. My solution was:
Suppose n = i*j, with i,j different from 1;
Therefore, setting b = 2j > 2, 2n = bi.
Hence 2n - 1 = bi - 1 = (b - 1)(bi-1 + ... + 1), and as i > 1 we have that both factors are greater than 1.
A little non-color coded hint for part (a): it is NOT hard... don't think too much, or you'll stray.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: NEW PROBLEM: PRIMES
« Reply #3 on: Nov 3rd, 2002, 8:58pm » |
Quote Modify
|
Okay, I'll bite on (a): if m is odd, then (xm + 1) = (x + 1) (xm-1 - xm-2+...+1)
So if n = mk, with m odd,
(2n+1) = (2k + 1)(2k(m-1) - ...)
This can only be if m=1, and thus n is a power of 2.
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print