Proving Prime Divisibility of 2^(2^n)+1

[Dragonfall]

Homework Statement

Prove that if a prime $$p|2^{2^n}+1$$ then $$p=2^{n+1}k+1$$ for some k.

Don't know how. I'm guessing by induction, perhaps?

 

[Dragonfall]

Anyone? I have no idea how to proceed.

 

[Gib Z]

Yep, induction. Prove the first statement is true for n, then assume true for n=k+1.

 

[tim_lou]

is k an integer?

 

[Dragonfall]

I don't see how this could be done by induction.

 

[tim_lou]

The problem seems interesting... however, I am also clueless about how to do this problem...

one suggestion is to assume all divisor in the form of:
$$2^{n+1}k+m$$

then prove m is one using long division dividing:
$$x^{2^n}+1$$
by
$$x^{n+1}k+m$$

where x=2...

or it may help to view things in binary.

 

[robert Ihnot]

I thought I saw this once somewhere, oops! It was about Mersenne Numbers.

Anyway, Euler was the first person to prove the form of the factors. Fermat had conjectured, 1650, that his "Fermat Number" was always prime for all values, but Euler show differently: N=5 gives: 4,294,967,297 = 641x6700417. In fact beside the early cases N=0 to N=4, no one has found anymore "Fermat Primes."

This is about the only know case where Fermat was wrong about a conjecture, but, perhaps, those thinking Fermat actually solved his "own Last Theorem," might take note of his failure with the above conjecture.

Actually the problem is not that dissimilar to the Mersenne one. In this case we have 2^(2^n)==-1 Mod q, so that squaring produces 2^(2^(n+1)) ==1 Mod q for some prime divisor q.

To the modulus q, we have q-1 is the complete residue system, and 2^(2^n) is less than q, since it gave the value -1. Therefore 2^(n+1) is a divisor of this system q-1. Thus q=K2^(n+1)+1.

Note: Some of the values I looked at have a much higher power of two, and Lucas showed the value could be raised by 1 to q=2^(n+2)+1.

 

[tim_lou]

oh, that's brilliant!

correct me if I am wrong:
basically, you show that,
$$2^{2^{n+1}}\equiv 1 \pmod {q}$$

since,
$$\text{ord}_q(2)|q-1, 2^{n+1}$$edit: mistakes. Sorry, but I do not understand group theories.. although I do have a little bit knowledge in number theory.

nevermind... I see.

 

[robert Ihnot]

The order of the element divides the order of the group. This is called Lagrange's Theorem. The order of the group is q-1. This is also connected with Fermat's Little Theorem: X^(p-1)==1 Mod p, for every element X, but some elements only need a smaller power than p-1, but a divisor of p-1.

 

[Dragonfall]

I understand your proof, but it seems like cheating to invoke group theory. Thanks though.