Results 1 to 2 of 2

Math Help - Probability of a square Mod

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    4

    Probability of a square Mod

    I really have no idea where to start , or how to do this problem.

    Suppose x is relatively prime to p; it's claimed when p is large that x is a square root mod p with probability of 1/2.

    I'm supposed to justify the claim.

    If anyone could help me with this it would be greatly appreciated.
    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
    You say that x is a square root mod p? That is true all of the time. x is the square root of x^2, mod p.

    What you probably mean is that x is a square mod p with probability 1/2. This is because there are as many nonzero squares as there are non-squares mod p (when p is odd).

    To see that this is true, notice that the nonzero squares mod p are precisely the roots of the polynomial x^{(p-1)/2}-1, which has no repeated roots.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Perfect Square Probability
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 2nd 2011, 02:50 PM
  2. Replies: 3
    Last Post: July 2nd 2011, 08:03 PM
  3. Replies: 5
    Last Post: June 10th 2010, 04:54 PM
  4. confidence interval chi square probability search
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 16th 2010, 11:04 PM
  5. Replies: 0
    Last Post: October 7th 2009, 08:45 PM

Search Tags


/mathhelpforum @mathhelpforum