Re: Need hints for a problem about primes.

From: Jon Haugsand (jonhaug_at_ifi.uio.no)
Date: 01/25/05 

Date: 25 Jan 2005 11:44:32 +0100

* Snis Pilbor
> Hello,
>
> 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.

I usually think such problems are easier to deal with when working
backwards. That is, suppose n is not a power of 2, can you then
factorize a^n+1?

Another hint: Play around with different values for a and n and look
for patterns.

Final hint: As another said, assume n is odd as a first approach.
Then you can assume that n=(2q+1)2^k which is the general expression
for a number that is not a power of 2.

If you also proved Israel's lemma, you should be home. 

-- 
Jon Haugsand
  Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug@ifi.uio.no
  http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92

Relevant Pages