# Proof question

• Sep 27th 2009, 03:40 PM
koukou8617
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
• Sep 30th 2009, 03:34 PM
Haven
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.
• Sep 30th 2009, 06:41 PM
koukou8617