Results 1 to 5 of 5

Thread: Legendre Symbol (Urgent)

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    33

    Legendre Symbol (Urgent)

    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)
    Last edited by Richmond; Oct 20th 2008 at 03:47 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2007
    Posts
    108
    I think you meant $\displaystyle F_n=(2)^{2^n}+1$
    Part a) Since $\displaystyle F_n$ is a prime, by Euler's criterion $\displaystyle 3^{\frac{F_n-1}{2}}\equiv(\frac{3}{F_n})(mod F_n)$
    Since $\displaystyle F_n=(2)^{2^n}+1\equiv1 (mod4)$
    By Law of Quadratic Reciprocity, $\displaystyle (\frac{3}{F_n})=(\frac{F_n}{3})=(\frac{(2)^{2^n}+1 }{3})$ (*)
    Since $\displaystyle 2\equiv-1 (mod 3)$
    (*)$\displaystyle =(\frac{(-1)^{2^n}+1}{3})=(\frac{1+1}{3})=(\frac{2}{3})=-1$
    Hence, $\displaystyle 3^{\frac{F_n-1}{2}}\equiv -1 (mod F_n)$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Richmond View Post
    (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.
    This makes no sense. Because if $\displaystyle q>3$ is a prime dividing $\displaystyle F_n$ then order of $\displaystyle 3$ is at most $\displaystyle q-1$. How can it be $\displaystyle F_n - 1 \geq q - 1$?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2007
    Posts
    108
    Richmond, can you check these two conditions given that $\displaystyle 3^{\frac{F_n-1}{2}}\equiv -1 (mod F_n)$
    1) $\displaystyle 3^{F_n-1}\equiv 1 (mod F_n)$.
    2) $\displaystyle 3^q$ is not congruent to $\displaystyle 1 (mod F_n)$ for proper divisor q of $\displaystyle F_n-1$
    I think that would show that $\displaystyle F_n$ is prime.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    33
    oh I'm sorry, got the question wrong

    Its 3^1/(2(Fn−1)) = -1 (mod Fn).

    Anyway what program do u guys use to put accurate mathematical symbols?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 16th 2011, 07:55 PM
  2. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Apr 12th 2010, 05:57 PM
  3. Legendre Symbol (5/p)
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Dec 11th 2009, 03:37 AM
  4. Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 02:56 PM
  5. legendre symbol
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 4th 2008, 06:01 AM

Search Tags


/mathhelpforum @mathhelpforum