1. ## Euler's criterion

For any integer $\displaystyle n \geq 2$, let $\displaystyle F_n = 2^{2^n}+1$ and let $\displaystyle p | F_n$ be any prime.

I can show that $\displaystyle ord_p{2} = 2^{n+1}$, however I'm struggling to answer the rest of the qestion:

1) Using Euler’s criterion show that $\displaystyle 2^{(p-1)/2} = 1$ mod p. It looks like we have to show $\displaystyle (\tfrac{{2}}{p})$ = 1, but how can we show this?

2) Deduce that $\displaystyle p = 1 + 2^{2+n}k$ for some $\displaystyle k \in N$ and use this to verfiy that $\displaystyle F_4$ is prime.

2. We have: $\displaystyle \left. p \right|F_n \Leftrightarrow 2^{2^n } \equiv - 1\left( {\bmod .p} \right)$ (1)

Now $\displaystyle 2^{2^n } \equiv - 1\left( {\bmod .p} \right) \Rightarrow \left( {2^{2^n } } \right)^2 = 2^{2^{n + 1} } \equiv 1\left( {\bmod .p} \right)$ and so: $\displaystyle k = {\text{ord}}_p 2$ satisfies: $\displaystyle \left. k \right|2^{n + 1}$ and therefore k is a power of 2: $\displaystyle k = 2^j$ with $\displaystyle j\in\mathbb{N}$

Assume: $\displaystyle j<n+1$ then $\displaystyle 2^{2^n } = \left( {2^{2^j } } \right)^{2^{n - j} } \equiv \left( 1 \right)^{2^{n - j} } = 1\left( {\bmod .p} \right)$ (because: $\displaystyle n-j\in\mathbb{N}$ ) and this contradicts (1), so $\displaystyle j=n+1$ and $\displaystyle 2^{n+1}= {\text{ord}}_p 2$

Now Fermat's Little Theorem Implies: $\displaystyle 2^{p - 1} \equiv 1\left( {\bmod .p} \right) \Rightarrow \left. {2^{n + 1} } \right|\left( {p - 1} \right)$ (*)

To prove 1) Note that (*) implies that if $\displaystyle n\geq 2$ then $\displaystyle \tfrac{{p^2 - 1}} {8}$ is even.

Thus, since $\displaystyle \left( {\tfrac{2} {p}} \right)_L = \left( { - 1} \right)^{\tfrac{{p^2 - 1}} {8}}$ we have: $\displaystyle \left( {\tfrac{2} {p}} \right)_L = 1$ and the rest follows by Euler's Criterion.

2) Part 1) implies that $\displaystyle k\left| {\left( {\tfrac{{p - 1}} {2}} \right)} \right. \Rightarrow p \equiv 1\left( {\bmod .2k} \right)\therefore p \equiv 1\left( {\bmod .2^{n + 2} } \right)$

3. Great, thanks. I don't quite see the application of this though - how do we use the last result to show that $\displaystyle F_4$ is prime? As far as I can see, we want to show that $\displaystyle (1+2^6k) | (1+ 2^{16})$ implies $\displaystyle k = 2^{10}$. Of course, there are only a finite number of cases to check so we could in theory just do this by brute force, but what's the nice way?

4. Originally Posted by Amanda1990
Great, thanks. I don't quite see the application of this though - how do we use the last result to show that $\displaystyle F_4$ is prime?
Oh, sorry, I forgot that part.

Well, you should know that if a number $\displaystyle n$ is not prime, then it has a prime divisor smaller or equal to $\displaystyle \sqrt{n}$. ( suppose it didn't, then since it is the product of at least to primes greater than $\displaystyle \sqrt{n}$ we get that $\displaystyle n>n$ which is a contradiction), now $\displaystyle F_4=2^{2^4}+1$ and $\displaystyle \sqrt{F_4}=\sqrt{2^{2^4}+1}$ clearly that 1 there is 'not very relevant' so we only have to check up to: $\displaystyle \left\lfloor {F_4 } \right\rfloor= \sqrt{2^{2^4}}=2^{2^3}=2^{8}=256$

Now all prime divisors of $\displaystyle F_4$ are of the form $\displaystyle p\equiv{1}(\bmod.2^{4+2})$ that is: $\displaystyle p\equiv{1}(\bmod.64)$, but neither $\displaystyle 65$ nor $\displaystyle 129$ are primes (clearly 5 divides 65, 3 divides 129 ), and so if $\displaystyle F_4$ were not prime, 193 should divide it ( since the next number of the form 64k+1 is 257), but you can check that 193 doesn't divide $\displaystyle F_4$