Results 1 to 2 of 2

Thread: 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
    10
    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 $\displaystyle p=4k+3$ it means $\displaystyle q=2(4k+3)+1 = 8k+7$ thus $\displaystyle q\equiv 7(\bmod 8)$. Therefore, $\displaystyle 2$ is a quadradic residue modulo $\displaystyle q$. Thus, there is a solution to $\displaystyle x^2 \equiv 2(\bmod q)$. Therefore, $\displaystyle 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 $\displaystyle q$ divides $\displaystyle 2^p - 1$. However, $\displaystyle 2^p-1$ can still be prime if $\displaystyle 2^p - 1 = q$. However, if $\displaystyle p>3$ then $\displaystyle 2^p - 1 > 2p+1 = q$ which would mean that $\displaystyle 2^p-1$ is not prime. The only way, therefore, for it to be prime is when $\displaystyle 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: Feb 8th 2011, 05:49 PM
  2. Quadratic residue mod 2^r
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 12th 2010, 08:37 PM
  3. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 10th 2010, 01:35 PM
  4. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Nov 25th 2009, 08:36 PM
  5. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 13th 2009, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum