Results 1 to 4 of 4

Math Help - Quadratic Residue Question

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    Quadratic Residue Question

    1) Show that a prime divisor p of the Fermat number F_{n} = 2^{2^n} + 1 must be of the form 2^{n+2}k + 1.

    (Hint: Show that ord_{p}2 = 2 ^{n+1}. Then show that 2^{(p-1)/2} is congruent to 1 (mod p). Conclude that 2^{n+1} \mid (p-1)/2)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    1) Show that a prime divisor p of the Fermat number F_{n} = 2^{2^n} + 1 must be of the form 2^{n+2}k + 1.

    (Hint: Show that ord_{p}2 = 2 ^{n+1}. Then show that 2^{(p-1)/2} is congruent to 1 (mod p). Conclude that 2^{n+1} \mid (p-1)/2)
    Well, the hint is pretty good. What did you try? Do you at least see how the hint would imply the solution?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2008
    Posts
    152
    Quote Originally Posted by Bruno J. View Post
    Well, the hint is pretty good. What did you try? Do you at least see how the hint would imply the solution?
    I understand the beginning of the hint, but I don't get how that implies the solution...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Janu42 View Post
    I understand the beginning of the hint, but I don't get how that implies the solution...
    Well, if u has order d modulo p, i.e. u is the least positive integer such that u^d\equiv 1 \mod p, then for any exponent l such that u^l\equiv 1\mod p, we must have l \mid d.

    Hence if 2^{(p-1)/2}\equiv 1 \mod p, this means that the order of 2 must divide (p-1)/2...

    Extra hint : to show that 2^{(p-1)/2}\equiv 1 \mod p, you can use the "second supplement" to the quadratic reciprocity law, which states that 2^{(p-1)/2}\equiv (-1)^{(p^2-1)/8} \mod p for any odd prime p.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. When is 2 a quadratic residue?
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 8th 2011, 05:49 PM
  2. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 10th 2010, 01:35 PM
  3. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 25th 2009, 08:36 PM
  4. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 13th 2009, 09:36 AM
  5. law of quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum