Results 1 to 2 of 2

Math Help - law of quadratic residue

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    46

    law of quadratic residue

    let p and q be prime numbers with p=3 mod 4 and q=2p + 1. Prove that 2^p -1 is a Mersenne prime if and only if p=3.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mndi1105 View Post
    let p and q be prime numbers with p=3 mod 4 and q=2p + 1. Prove that 2^p -1 is a Mersenne prime if and only if p=3.
    Since p=4k+3 it means q=2(4k+3)+1 = 8k+7 thus q\equiv 7(\bmod 8). Therefore, 2 is a quadradic residue modulo q. Thus, there is a solution to x^2 \equiv 2(\bmod q). Therefore, 2^p = 2^{(q-1)/2} \equiv \left( x^2 \right)^{(q-1)/2} \equiv x^{q-1} \equiv 1(\bmod q). Therefore, we see that q divides 2^p - 1. However, 2^p-1 can still be prime if 2^p - 1 = q. However, if p>3 then 2^p - 1 > 2p+1 = q which would mean that 2^p-1 is not prime. The only way, therefore, for it to be prime is when p=3.
    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 mod 2^r
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 12th 2010, 08:37 PM
  3. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 10th 2010, 01:35 PM
  4. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 25th 2009, 08:36 PM
  5. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 13th 2009, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum