Results 1 to 3 of 3

Math Help - Congruence Proof using Wilson's Theorem

  1. #1
    Junior Member
    Joined
    Jul 2008
    Posts
    74

    Congruence Proof using Wilson's Theorem

    Dear all,

    I'm having trouble completing the proof for the following result, that requires Wilson's Theorem. I've shown this, along with my work, below.

    Thank you!

    scherz0

    --------

    For any odd prime  p , show that:
    1^2 \cdot 3^2 \cdot ... \cdot (p - 2)^2 \equiv 2^2 \cdot 4^2 \cdot ... \cdot (p - 1)^2 \equiv (-1)^{\frac{p+1}{2}}

    Work: By Wilson's Theorem, I know that: p prime  \Longleftrightarrow (p - 1)! \equiv -1\pmod {p} \Longleftrightarrow (p - 2)! \equiv 1\pmod {p} .

    Also, for any k, I know that  p - k \equiv -k\pmod {p}. This means that:

     p - 1 \equiv -1\pmod {p}, p - 2 \equiv -2\pmod {p}, p - 3 \equiv -3\pmod {p} \implies (p - 1)(p - 2)(p - 3)... \equiv (-1)(-2)(-3)... \pmod{p}

    But I can't see how to apply the results above to prove the congruence relation?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by scherz0 View Post
    Dear all,

    I'm having trouble completing the proof for the following result, that requires Wilson's Theorem. I've shown this, along with my work, below.

    Thank you!

    scherz0

    --------

    For any odd prime  p , show that:
    1^2 \cdot 3^2 \cdot ... \cdot (p - 2)^2 \equiv 2^2 \cdot 4^2 \cdot ... \cdot (p - 1)^2 \equiv (-1)^{\frac{p+1}{2}}

    Work: By Wilson's Theorem, I know that: p prime  \Longleftrightarrow (p - 1)! \equiv -1\pmod {p} \Longleftrightarrow (p - 2)! \equiv 1\pmod {p} .

    Also, for any k, I know that  p - k \equiv -k\pmod {p}. This means that:

     p - 1 \equiv -1\pmod {p}, p - 2 \equiv -2\pmod {p}, p - 3 \equiv -3\pmod {p} \implies (p - 1)(p - 2)(p - 3)... \equiv (-1)(-2)(-3)... \pmod{p}

    But I can't see how to apply the results above to prove the congruence relation?

    RHS, working all the time with arithmetic modulo p:

    \displaystyle{2^2\cdot 4^2\cdot\ldots\cdot (p-1)^2=2\cdot 4\cdot\ldots\cdot (p-1)(p-1)(p-3)\cdot\ldots\cdot [-(p-2]=

    \displaystyle{=(-1)^{\frac{p-1}{2}}(p-1)!=(-1)^{\frac{p+1}{2}}

    Now you do the LHS...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2008
    Posts
    74
    Quote Originally Posted by tonio View Post
    RHS, working all the time with arithmetic modulo p:

    \displaystyle{2^2\cdot 4^2\cdot\ldots\cdot (p-1)^2=2\cdot 4\cdot\ldots\cdot (p-1)(p-1)(p-3)\cdot\ldots\cdot [-(p-2]
    \displaystyle{=(-1)^{\frac{p-1}{2}}(p-1)!=(-1)^{\frac{p+1}{2}}

    Now you do the LHS...

    Tonio
    Thanks for your response, Tonio.

    However, could you explain more on:

    \displaystyle{2^2\cdot 4^2\cdot\ldots\cdot (p-1)^2=2\cdot  4\cdot\ldots\cdot (p-1)(p-1)(p-3)\cdot\ldots\cdot [-(p-2]?

    From what I see, I think that we are separating the powers so that:

     2^2 \cdot 4^2 \cdot ... \cdot (p - 1)^2 \equiv 2\cdot 4 ... \cdot (p - 1) \cdot 2 \cdot 4 \cdot ... \cdot (p - 1) \pmod {p}.

    But why are there:

    1) a (p - 3) after the two (p - 1)s and

    2) -(p - 2), since your post was about the RHS only?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving Wilson's theorem.
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 11th 2010, 06:30 PM
  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's theorem proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 16th 2009, 05:48 AM
  4. Replies: 1
    Last Post: March 9th 2009, 12:51 PM
  5. Help with proof using Wilson's theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 23rd 2009, 03:05 PM

Search Tags


/mathhelpforum @mathhelpforum