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 $\displaystyle F_n=(2)^{2^n}+1$
Part a) Since $\displaystyle F_n$ is a prime, by Euler's criterion $\displaystyle 3^{\frac{F_n-1}{2}}\equiv(\frac{3}{F_n})(mod F_n)$
Since $\displaystyle F_n=(2)^{2^n}+1\equiv1 (mod4)$
By Law of Quadratic Reciprocity, $\displaystyle (\frac{3}{F_n})=(\frac{F_n}{3})=(\frac{(2)^{2^n}+1 }{3})$ (*)
Since $\displaystyle 2\equiv-1 (mod 3)$
(*)$\displaystyle =(\frac{(-1)^{2^n}+1}{3})=(\frac{1+1}{3})=(\frac{2}{3})=-1$
Hence, $\displaystyle 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 $\displaystyle q>3$ is a prime dividing $\displaystyle F_n$ then order of $\displaystyle 3$ is at most $\displaystyle q-1$. How can it be $\displaystyle F_n - 1 \geq q - 1$?

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