Results 1 to 4 of 4

Thread: Euler's criterion

  1. #1
    Member
    Joined
    Feb 2009
    Posts
    103

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

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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)
    $
    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 $\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?
    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 $\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$
    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: Nov 4th 2010, 08:44 PM
  2. Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Mar 30th 2010, 01:57 PM
  3. Replies: 0
    Last Post: Sep 17th 2009, 06:44 PM
  4. Quadratic Reciprocity/ Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 02:59 PM
  5. Quadratic Reciprocity/ Euler's Criterion
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum