Proof involving Wilson's theorem.

• Dec 10th 2010, 10:07 PM
HelloWorld2
Proof involving Wilson's theorem.
Hey, I was just wondering gif someone could help me prove the following.

((p-1)/2)!)^ 2=(+ or -) 1 mod (p), where p is prime.

THanks
• Dec 11th 2010, 02:39 AM
tonio
Quote:

Originally Posted by HelloWorld2
Hey, I was just wondering gif someone could help me prove the following.

((p-1)/2)!)^ 2=(+ or -) 1 mod (p), where p is prime.

THanks

For p an odd prime, we have:

$\displaystyle \displaystyle{(p-1)! = 1\cdot 2\cdot\ldots\cdot(p-1)=1\cdot\ldots\cdot \frac{p-1}{2}\cdot \frac{p+1}{2}\cdot\ldots\cdot (p-1)!=(-1)^{\frac{p-1}{2}}\left(1\cdot\ldots\cdot \frac{p-1}{2}\right)^2}$ (why?),

so...

Tonio

Pd. If you in fact understand the above, then you must be able even to tell when exactly we'll

get 1 and when -1 modulo p.
• Dec 11th 2010, 09:04 AM
HelloWorld2
well, we'll get 1 when p=1mod(4), and -1 when p=-1mod(4). I realy don't get how you got that equaility.
• Dec 11th 2010, 10:55 AM
tonio
Quote:

Originally Posted by HelloWorld2
well, we'll get 1 when p=1mod(4), and -1 when p=-1mod(4). I realy don't get how you got that equaility.

What're the inverses modulo p of $\displaystyle 1\,,\,2\,\ldots,\frac{p-1}{2}$ ? Well, there you go.

Tonio
• Dec 11th 2010, 02:53 PM
melese
Quote:

Originally Posted by tonio
What're the inverses modulo p of $\displaystyle 1\,,\,2\,\ldots,\frac{p-1}{2}$ ? Well, there you go.

Tonio

But, for example, $\displaystyle 3\cdot4\equiv1\pmod{11}$, and $\displaystyle \displaystyle3,4\leq\frac{11-1}{2}$ (If I understand what you meant.).

The observation here is that for $\displaystyle \displaystyle1\leq x\leq\frac{p-1}{2}$, we have $\displaystyle \displaystyle\frac{p+1}{2}\leq p-x\leq p-1$.
Then noting that $\displaystyle p-x\equiv-x\pmod p$ shows that $\displaystyle \displaystyle\frac{p+1}{2}\cdots(p-2)(p-1)\equiv(-\frac{p-1}{2})\cdots(-2)(-1)\pmod p$.
• Dec 11th 2010, 06:30 PM
tonio
Quote:

Originally Posted by melese
But, for example, $\displaystyle 3\cdot4\equiv1\pmod{11}$, and $\displaystyle \displaystyle3,4\leq\frac{11-1}{2}$ (If I understand what you meant.).

I don't think you do, but for sure I don't understand you: "inverse" means "additive inverse", not "multiplicative inverse", as

I think it was clear from the context of my answer, so your example is irrelevant, I believe, and what is relevant is what you wrote

after that, which is what I was trying the OP to realize by himself.

Tonio

The observation here is that for $\displaystyle \displaystyle1\leq x\leq\frac{p-1}{2}$, we have $\displaystyle \displaystyle\frac{p+1}{2}\leq p-x\leq p-1$.
Then noting that $\displaystyle p-x\equiv-x\pmod p$ shows that $\displaystyle \displaystyle\frac{p+1}{2}\cdots(p-2)(p-1)\equiv(-\frac{p-1}{2})\cdots(-2)(-1)\pmod p$.

.