wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Primes
        
(Message started by: Pietro K.C. on Sep 19^th, 2002, 12:24pm)

Title: Primes
Post by Pietro K.C. on Sep 19^th, 2002, 12:24pm

a) Prove that, if 2ⁿ + 1 is a prime, then n is a power of 2.

b) Prove that, for positive integers a, n with n > 1, if aⁿ - 1 is prime, then a = 2 and n is prime.

Title: Re: NEW PROBLEM: PRIMES
Post by TimMann on Oct 16^th, 2002, 1:04am

(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 aⁿ-1 in base a. What does it look like?

Solution for (b):

(aⁿ - 1) = (a - 1) (a^n-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

(a^j-1 + a^j-2 + ... + 1) * (a^n-j + a^n-2j + ... + 1)

Title: Re: NEW PROBLEM: PRIMES
Post by Pietro K.C. on Oct 16^th, 2002, 7:39am

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 = 2^j > 2, 2ⁿ = bⁱ.

Hence 2ⁿ - 1 = bⁱ - 1 = (b - 1)(b^i-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. :)

Title: Re: NEW PROBLEM: PRIMES
Post by Icarus on Nov 3^rd, 2002, 8:58pm

Okay, I'll bite on (a): if m is odd, then (x^m + 1) = (x + 1) (x^m-1 - x^m-2+...+1)
So if n = mk, with m odd,
(2ⁿ+1) = (2^k + 1)(2^k(m-1) - ...)
This can only be if m=1, and thus n is a power of 2.