Results 1 to 3 of 3

Thread: Proof question

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    19

    Proof question

    Recall the definition of n! (read n factorial"):
    n! = (n)(n-1)(n-2) .(2)(1) =∏(k)
    In both (a) and (b) below, suppose p≥3 is prime.
    (a) Prove that if x∈ Zpx is a solution to x square ≡1 (mod p), then x ≡1 (mod p).
    (b) Prove that (p-1)!≡1 (mod p)

    Zpx x shoud be above p
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    Okay, Correct me if I'm wrong, but the two question are
    Let p be prime.
    1) If $\displaystyle x\in\mathbb{Z}_{p} $ and $\displaystyle x^{2}\equiv\\1$ (mod p) then $\displaystyle x\equiv\pm\\1$ (mod p)
    2) $\displaystyle (p - 1)!\equiv\pm\\1$ (mod p)

    For 1 we get
    $\displaystyle x^{2}\equiv\\1$ (mod p)
    $\displaystyle \Rightarrow\\x^{2} -1\equiv\\0 $ (mod p)
    $\displaystyle \Rightarrow\\(x-1)(x+1)\equiv\\0$ (mod p)
    $\displaystyle \Rightarrow\\p|(x-1)(x+1) $
    $\displaystyle \Rightarrow\\p|(x-1) $ or $\displaystyle p|(x+1) $
    $\displaystyle \Rightarrow\\x\equiv\\1 $ (mod p) or $\displaystyle x\equiv\\-1 $ (mod p)
    $\displaystyle \Rightarrow\\x\equiv\pm\\1 $ (mod p)

    2) is wrong. The correct version is $\displaystyle (p - 1)!\equiv\\1$ (mod p), the result is known as Wilson's Theorem
    $\displaystyle (p-1)! = 1*2*3........(p-2)(p-1) $
    Now 1 and p-1 are the only numbers modulo p that are their own inverses.
    For any other number x such that $\displaystyle 1<x<p-1$ there exists $\displaystyle x^{-1}$ such that $\displaystyle 1<x^{-1}<p-1$ and $\displaystyle x*x^{-1}\equiv\\1$ (mod p).
    So we match up each x with its inverse and we get:
    $\displaystyle (p-1)!\equiv\\1*2*3........(p-2)(p-1)\equiv\\1*1*1.......(p-1)\equiv\\p-1\equiv\\-1$ (mod p)
    Now we have the desired result.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    19
    Thank you for your answer

    but for the second one

    it is Wilson's theorem like you said

    but the right one should be (p-1)!≡-1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof Question 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 29th 2009, 06:47 AM
  2. Another proof question
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Dec 21st 2008, 10:19 PM
  3. Proof question
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: Nov 5th 2008, 04:31 PM
  4. [SOLVED] Proof Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 29th 2006, 09:56 AM
  5. Proof Question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Mar 19th 2006, 05:54 AM

Search Tags


/mathhelpforum @mathhelpforum