Results 1 to 4 of 4

Math Help - Problem (Wilson's)

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    8

    Problem (Wilson's)

    Let p be an odd prime. Prove that the quadratic congruence x^2+1 \equiv 0\pmod{p} has a solution if and only if p \equiv1 \pmod{4}. (hint: use Wilson's theorem)
    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
    Wilson's theorem states that (p-1)!\equiv -1 \mod p. Since p-1 \equiv 0 \mod 4 we can regroup the terms in the product (p-1)! in pairs, as [1\times(p-1)][2 \times (p-2)]\dots\left[\frac{p-1}{2}\times \frac{p-1}{2}\right] \equiv (-1^2)(-2^2)\dots\left(-\left(\frac{p-1}{2}\right)^2\right) \mod p.

    Can you take it from there?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    8
    Alright, I have the <= direction.

    For the => direction, i have worked with wilson's down to
    (k!)^2\equiv-1 (mod p) where k=\frac{p-1}{2} but can't quite see how to get to the required conclusion of p\equiv1 (mod 4)
    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
    Well if a^d \equiv 1 \mod p and a^j \not\equiv 1 \mod p for 1 \leq j < d then we always must have d|p-1. What can you say about the order of x mod p if x^2\equiv -1 \mod p?
    Last edited by Bruno J.; March 5th 2010 at 11:17 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: November 30th 2011, 11:26 AM
  2. Regarding Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: August 5th 2010, 02:53 PM
  3. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 03:30 AM
  4. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 23rd 2008, 08:52 AM
  5. More on Wilson and Fermat
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 23rd 2008, 08:07 PM

Search Tags


/mathhelpforum @mathhelpforum