Re: Need hints for a problem about primes.

From: Don Taylor (dont_at_agora.rdrop.com)
Date: 01/25/05 

Date: Tue, 25 Jan 2005 01:47:16 -0600

"Snis Pilbor" <snispilbor@yahoo.com> writes:
>I am clawing my hair out trying to figure this out. The problem
>is to prove that if a^n+1 is prime (a>1) then n is a power of 2. I
>honestly don't even know where to start. Certainly this would imply
>a^n == -1 (p) [where prime p is just a^n+1, but we "forget" this
>relationship with a and just focus on the fact that a^n is -1 mod 'some
>prime'], and this is the only starting point I can think of, but this
>is a long long way away from a solution and I'm hopelessly stumped of
>even what broad, general strategy to use. Other grasps in the dark
>include observing that a^2n == 1 (p), and if we can show 2n is a power
>of 2 we're done, but this too leads nowhere; and that we can safely
>assume a is itself not a nontrivial power of anything (or just pull
>that power into n). Obviously a is even.

>Fair warning: this problem DOES arise amid homework. I'm just
>hoping for a hint or clue...

Well, what if n were odd? Can you get anything from that?
Can that let you make a tiny bit of progress.