Author 
Topic: Primes (Read 764 times) 

Pietro K.C.
Full Member
Gender:
Posts: 213

a) Prove that, if 2^{n} + 1 is a prime, then n is a power of 2. b) Prove that, for positive integers a, n with n > 1, if a^{n}  1 is prime, then a = 2 and n is prime.

« Last Edit: Nov 7^{th}, 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 16^{th}, 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 a^{n}1 in base a. What does it look like? Solution for (b): (a^{n}  1) = (a  1) (a^{n1} + ... + 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^{j1} + a^{j2} + ... + 1) * (a^{nj} + a^{n2j} + ... + 1)


IP Logged 
http://timmann.org/



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: NEW PROBLEM: PRIMES
« Reply #2 on: Oct 16^{th}, 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 = 2^{j} > 2, 2^{n} = b^{i}. Hence 2^{n}  1 = b^{i}  1 = (b  1)(b^{i1} + ... + 1), and as i > 1 we have that both factors are greater than 1. A little noncolor 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 3^{rd}, 2002, 8:58pm » 
Quote Modify

Okay, I'll bite on (a): if m is odd, then (x^{m} + 1) = (x + 1) (x^{m1}  x^{m2}+...+1) So if n = mk, with m odd, (2^{n}+1) = (2^{k} + 1)(2^{k(m1)}  ...) 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



