• Nov 10th 2010, 04:19 PM
Janu42
1) Show that a prime divisor p of the Fermat number $F_{n} = 2^{2^n} + 1$ must be of the form $2^{n+2}k + 1$.

(Hint: Show that $ord_{p}2 = 2 ^{n+1}$. Then show that $2^{(p-1)/2}$ is congruent to 1 (mod p). Conclude that $2^{n+1} \mid$ (p-1)/2)
• Nov 11th 2010, 09:26 AM
Bruno J.
Quote:

Originally Posted by Janu42
1) Show that a prime divisor p of the Fermat number $F_{n} = 2^{2^n} + 1$ must be of the form $2^{n+2}k + 1$.

(Hint: Show that $ord_{p}2 = 2 ^{n+1}$. Then show that $2^{(p-1)/2}$ is congruent to 1 (mod p). Conclude that $2^{n+1} \mid$ (p-1)/2)

Well, the hint is pretty good. What did you try? Do you at least see how the hint would imply the solution?
• Nov 11th 2010, 11:29 AM
Janu42
Quote:

Originally Posted by Bruno J.
Well, the hint is pretty good. What did you try? Do you at least see how the hint would imply the solution?

I understand the beginning of the hint, but I don't get how that implies the solution...
• Nov 11th 2010, 03:50 PM
Bruno J.
Quote:

Originally Posted by Janu42
I understand the beginning of the hint, but I don't get how that implies the solution...

Well, if $u$ has order $d$ modulo $p$, i.e. $u$ is the least positive integer such that $u^d\equiv 1 \mod p$, then for any exponent $l$ such that $u^l\equiv 1\mod p$, we must have $l \mid d$.

Hence if $2^{(p-1)/2}\equiv 1 \mod p$, this means that the order of $2$ must divide $(p-1)/2$...

Extra hint : to show that $2^{(p-1)/2}\equiv 1 \mod p$, you can use the "second supplement" to the quadratic reciprocity law, which states that $2^{(p-1)/2}\equiv (-1)^{(p^2-1)/8} \mod p$ for any odd prime $p$.