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.
Thanks in advance.
Got the question wrong, my bad. (Edited)