# Math Help - Quadratic Residue Question

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)

2. 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?

3. 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...

4. 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$.