# Quadratic Residue Question

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

(Hint: Show that $\displaystyle ord_{p}2 = 2 ^{n+1}$. Then show that $\displaystyle 2^{(p-1)/2}$ is congruent to 1 (mod p). Conclude that $\displaystyle 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 $\displaystyle F_{n} = 2^{2^n} + 1$ must be of the form $\displaystyle 2^{n+2}k + 1$.

(Hint: Show that $\displaystyle ord_{p}2 = 2 ^{n+1}$. Then show that $\displaystyle 2^{(p-1)/2}$ is congruent to 1 (mod p). Conclude that $\displaystyle 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 $\displaystyle u$ has order $\displaystyle d$ modulo $\displaystyle p$, i.e. $\displaystyle u$ is the least positive integer such that $\displaystyle u^d\equiv 1 \mod p$, then for any exponent $\displaystyle l$ such that $\displaystyle u^l\equiv 1\mod p$, we must have $\displaystyle l \mid d$.

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

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