# Thread: Euler's criterion

1. ## Euler's criterion

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

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

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

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

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

Now $
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: $
k = {\text{ord}}_p 2
$
satisfies: $
\left. k \right|2^{n + 1}
$
and therefore k is a power of 2: $
k = 2^j
$
with $j\in\mathbb{N}$

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

Now Fermat's Little Theorem Implies: $
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 $n\geq 2$ then $
\tfrac{{p^2 - 1}}
{8}
$
is even.

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

2) Part 1) implies that $
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 $F_4$ is prime? As far as I can see, we want to show that $(1+2^6k) | (1+ 2^{16})$ implies $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 $F_4$ is prime?
Oh, sorry, I forgot that part.

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

Now all prime divisors of $F_4$ are of the form $p\equiv{1}(\bmod.2^{4+2})$ that is: $p\equiv{1}(\bmod.64)$, but neither $65$ nor $129$ are primes (clearly 5 divides 65, 3 divides 129 ), and so if $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 $F_4$