wu :: forums
« wu :: forums - Primes »

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 3:55pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: william wu, SMQ, towr, Eigenray, Grimbal, Icarus)
   Primes
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Primes  (Read 760 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Primes  
« on: Sep 19th, 2002, 12:24pm »
Quote Quote Modify Modify

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
****






   
WWW

Gender: male
Posts: 330
Re: NEW PROBLEM: PRIMES  
« Reply #1 on: Oct 16th, 2002, 1:04am »
Quote Quote Modify 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
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PROBLEM: PRIMES  
« Reply #2 on: Oct 16th, 2002, 7:39am »
Quote Quote Modify 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? Smiley
 
   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. Smiley
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: male
Posts: 4863
Re: NEW PROBLEM: PRIMES  
« Reply #3 on: Nov 3rd, 2002, 8:58pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board