Results 1 to 5 of 5

Math Help - [SOLVED] Wilson theorem Question Explanation

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    5

    [SOLVED] Wilson theorem Question Explanation

    Use:
    2\cdot4\cdot...\cdot(p-1)\equiv(2-p)(4-p)\cdot...\cdot(p-1-p)\equiv(-1)^{\frac{(p-1)}{2}}\cdot1\cdot3\cdot...\cdot(p-2) mod p
    and
    (p-1)!\equiv-1 mod p [Wilson's Theorem]
    to prove
    1^2\cdot3^2\cdot5^2\cdot...\cdot(p-2)^2\equiv(-1)^{\frac{(p-1)}{2}} mod p



    Relevant equations

    Gauss lemma
    wilson's theorem [ (p-1)!\equiv-1 mod p]



    The attempt at a solution
    need assistance


    Thanks
    Last edited by mathsss2; November 2nd 2008 at 10:05 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    2 \cdot 4 \cdot \cdots \cdot (p-1)

    ...... \equiv (2 - p)(4 - p) \cdots ((p-1)-p) \ (\text{mod }p) (simply subtracting the modulus to each term)

    ...... \equiv (-1)(p-2) \cdot (-1)(p-4) \cdot (-1)(p -6) \cdots \cdot (-1)(1) \ (\text{mod } p) (Factor out -1 from each term)

    Now, notice that all the numbers from 1 to (p-1) are all least residues of p. We have half the numbers since all the even numbers from 1 to (p-1) are gone, leaving us with \frac{p-2}{2} odd terms (1, 3, 7, ... , p-2 ) and thus \frac{p-2}{2} factors of -1. So:

    ...... \equiv (-1)^{(p-1)/2} \cdot 1 \cdot 3 \cdot \cdots \cdot (p-2) \ (\text{mod } p)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    5
    Thanks a lot
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by mathsss2 View Post
    and
    (p-1)!\equiv-1 mod p [Wilson's Theorem]
    to prove
    1^2\cdot3^2\cdot5^2\cdot...\cdot(p-2)^2\equiv(-1)^{\frac{(p-1)}{2}} mod p
    Using what o_O we can finish this problem.

    Note (p-1)! = \left\{ 1\cdot 3 \cdot ... \cdot (p-2) \right\} \left\{ 2\cdot 4\cdot  ... \cdot (p-2) \right\} \equiv (-1)^{(p-1)/2} 1^2\cdot 3^2 \cdot ... \cdot (p-2)^2 (\bmod p)

    Thus, (-1)^{(p-1)/2} 1^2\cdot 3^2 \cdot ... \cdot (p-2)^2 \equiv - 1  \implies 1^2\cdot 3^2 \cdot ... \cdot (p-2)^2 \equiv (-1)^{(p+1)/2} (\bmod p)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2008
    Posts
    5
    Thanks for the help! This problem is now solved. Thanks a lot.
    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, 10:26 AM
  2. Prove Wilson's theorem by Lagrange's theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2010, 01:07 PM
  3. Wilson theorem
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 16th 2009, 02:30 AM
  4. [SOLVED] Wilson's Theorem Question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 2nd 2008, 10:33 PM
  5. Wilson's Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 23rd 2008, 07:52 AM

Search Tags


/mathhelpforum @mathhelpforum