# Math Help - Legendre Symbol (Urgent)

1. ## Legendre Symbol (Urgent)

Let Fn = 2^(2n) + 1, the nth Fermat number. The following is used as a test for the primeness of Fn. Fn is prime if and only if 3^1/(2(Fn−1)) = −1 (mod Fn).

Prove the validity of the test as follows:
(a) If Fn is prime, calculate the Legendre symbol 3/Fn and so show that 3^1/(2(Fn−1)) = -1 (mod Fn)

(b) If 3^(1/2(Fn−1)) = -1 (mod Fn), and q is any prime dividing Fn, show that the order of 3 modulo q is Fn − 1 and so deduce that Fn is prime.

Got the question wrong, my bad. (Edited)

2. I think you meant $F_n=(2)^{2^n}+1$
Part a) Since $F_n$ is a prime, by Euler's criterion $3^{\frac{F_n-1}{2}}\equiv(\frac{3}{F_n})(mod F_n)$
Since $F_n=(2)^{2^n}+1\equiv1 (mod4)$
By Law of Quadratic Reciprocity, $(\frac{3}{F_n})=(\frac{F_n}{3})=(\frac{(2)^{2^n}+1 }{3})$ (*)
Since $2\equiv-1 (mod 3)$
(*) $=(\frac{(-1)^{2^n}+1}{3})=(\frac{1+1}{3})=(\frac{2}{3})=-1$
Hence, $3^{\frac{F_n-1}{2}}\equiv -1 (mod F_n)$

3. Originally Posted by Richmond
(b) If 3^(1/2(Fn−1)) = 1 (mod Fn), and q is any prime dividing Fn, show that the order of 3 modulo q is Fn − 1 and so deduce that Fn is prime.
This makes no sense. Because if $q>3$ is a prime dividing $F_n$ then order of $3$ is at most $q-1$. How can it be $F_n - 1 \geq q - 1$?

4. Richmond, can you check these two conditions given that $3^{\frac{F_n-1}{2}}\equiv -1 (mod F_n)$
1) $3^{F_n-1}\equiv 1 (mod F_n)$.
2) $3^q$ is not congruent to $1 (mod F_n)$ for proper divisor q of $F_n-1$
I think that would show that $F_n$ is prime.

5. oh I'm sorry, got the question wrong

Its 3^1/(2(Fn−1)) = -1 (mod Fn).

Anyway what program do u guys use to put accurate mathematical symbols?