wu :: forums « wu :: forums - Primes » Welcome, Guest. Please Login or Register. Oct 4th, 2023, 1:20pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: SMQ, Grimbal, Eigenray, william wu, Icarus, towr)    Primes « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Primes  (Read 764 times)
Pietro K.C.
Full Member

Gender:
Posts: 213
 Primes   « on: Sep 19th, 2002, 12:24pm » Quote 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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »