Results 1 to 4 of 4

Math Help - Euler's criterion

  1. #1
    Member
    Joined
    Feb 2009
    Posts
    103

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    We have: <br />
\left. p \right|F_n  \Leftrightarrow 2^{2^n }  \equiv  - 1\left( {\bmod .p} \right)<br />
(1)

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

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

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

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

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

    2) Part 1) implies that <br />
k\left| {\left( {\tfrac{{p - 1}}<br />
{2}} \right)} \right. \Rightarrow p \equiv 1\left( {\bmod .2k} \right)\therefore p \equiv 1\left( {\bmod .2^{n + 2} } \right)<br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Feb 2009
    Posts
    103
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by Amanda1990 View Post
    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: <br />
\left\lfloor {F_4 } \right\rfloor=<br />
\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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euler's criterion
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 4th 2010, 09:44 PM
  2. Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: March 30th 2010, 02:57 PM
  3. Replies: 0
    Last Post: September 17th 2009, 07:44 PM
  4. Quadratic Reciprocity/ Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 03:59 PM
  5. Quadratic Reciprocity/ Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 03:52 PM

Search Tags


/mathhelpforum @mathhelpforum