Quadratic Residue Question

**Janu42** · November 10th 2010, 04:19 PM

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)

**Bruno J.** · November 11th 2010, 09:26 AM

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?

**Janu42** · November 11th 2010, 11:29 AM

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

**Bruno J.** · November 11th 2010, 03:50 PM

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

Thread: Quadratic Residue Question

LinkBack

Thread Tools

Display

Quadratic Residue Question

Similar Math Help Forum Discussions

When is 2 a quadratic residue?

Quadratic residue -5

Quadratic Residue

quadratic non residue

law of quadratic residue

Search Tags