Results 1 to 5 of 5

Math Help - 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; October 20th 2008 at 04:47 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2007
    Posts
    108
    I think you meant F_n=(2)^{2^n}+1
    Part a) Since F_n is a prime, by Euler's criterion 3^{\frac{F_n-1}{2}}\equiv(\frac{3}{F_n})(mod F_n)
    Since F_n=(2)^{2^n}+1\equiv1 (mod4)
    By Law of Quadratic Reciprocity, (\frac{3}{F_n})=(\frac{F_n}{3})=(\frac{(2)^{2^n}+1  }{3}) (*)
    Since 2\equiv-1 (mod 3)
    (*) =(\frac{(-1)^{2^n}+1}{3})=(\frac{1+1}{3})=(\frac{2}{3})=-1
    Hence, 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 q>3 is a prime dividing F_n then order of 3 is at most q-1. How can it be 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 3^{\frac{F_n-1}{2}}\equiv -1 (mod F_n)
    1) 3^{F_n-1}\equiv 1 (mod F_n).
    2)  3^q is not congruent to  1 (mod F_n) for proper divisor q of F_n-1
    I think that would show that 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, 08:55 PM
  2. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 12th 2010, 06:57 PM
  3. Legendre Symbol (5/p)
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 11th 2009, 04:37 AM
  4. Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 11th 2009, 03:56 PM
  5. legendre symbol
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 4th 2008, 07:01 AM

Search Tags


/mathhelpforum @mathhelpforum