Results 1 to 2 of 2

Thread: 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 $\displaystyle x$ is a square root mod $\displaystyle p$? That is true all of the time. $\displaystyle x$ is the square root of $\displaystyle x^2$, mod $\displaystyle p$.

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

    To see that this is true, notice that the nonzero squares mod $\displaystyle p$ are precisely the roots of the polynomial $\displaystyle 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: Oct 2nd 2011, 01:50 PM
  2. Replies: 3
    Last Post: Jul 2nd 2011, 07:03 PM
  3. Replies: 5
    Last Post: Jun 10th 2010, 03:54 PM
  4. confidence interval chi square probability search
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Apr 16th 2010, 10:04 PM
  5. Replies: 0
    Last Post: Oct 7th 2009, 07:45 PM

Search Tags


/mathhelpforum @mathhelpforum