# Wilson's Theorem

• Nov 30th 2011, 07:34 AM
UNLVRich
Wilson's Theorem
So I've been working on this problem for too long now and I need some advice as to how to proceed. I've tried using induction and I've also tried plugging in concrete values to try and discern a pattern to no avail. I DO know that Wilson's Theorem applies.

Wilson's Theorem
If p is a prime, then (p-1)! $\displaystyle \equiv$ -1 (mod p)

Problem
Show that if p is an odd prime and a and b are non negative integers with a+b=p-1, then a!b! + (-1)^a $\displaystyle \equiv$ 0 (mod p)
• Nov 30th 2011, 09:26 AM
PaulRS
Re: Wilson's Theorem
Note that: $\displaystyle a! = 1\cdot ... \cdot a \equiv_p \left( (-1) \cdot (p-1) \right)\cdot .. \cdot \left( (-1) \cdot (p-a) \right)$ and that $\displaystyle p-a = b + 1$

(Wink)
• Nov 30th 2011, 09:42 AM
UNLVRich
Re: Wilson's Theorem
Quote:

Originally Posted by PaulRS
Note that: $\displaystyle a! = 1\cdot ... \cdot a \equiv_p \left( (-1) \cdot (p-1) \right)\cdot .. \cdot \left( (-1) \cdot (p-a) \right)$ and that $\displaystyle p-a = b + 1$

(Wink)

I tried factoring out the (-1) getting a! congruent to (-1)^a[(p-1)...(p-a)]. Then I tried to multiply by b! considering that p-a=b+1, but I'm getting nowhere. Man I feel stupid!
• Nov 30th 2011, 09:53 AM
alexmahone
Re: Wilson's Theorem
Quote:

Originally Posted by PaulRS
Note that: $\displaystyle a! = 1\cdot ... \cdot a \equiv_p \left( (-1) \cdot (p-1) \right)\cdot .. \cdot \left( (-1) \cdot (p-a) \right)$ and that $\displaystyle p-a = b + 1$

I'm going to try to complete this.

$\displaystyle a!\equiv (-1)^a(p-1)\cdots(p-a)\pmod{p}$

$\displaystyle a!b!\equiv (-1)^a(p-1)\cdots(p-a)b!\pmod{p}$

$\displaystyle \equiv (-1)^a(p-1)!\pmod{p}$ (Note that $\displaystyle p-a = b + 1$.)

$\displaystyle \equiv -(-1)^a\pmod{p}$ (Using Wilson's theorem)

$\displaystyle a!b!+(-1)^a\equiv 0\pmod{p}$
• Nov 30th 2011, 10:19 AM
UNLVRich
Re: Wilson's Theorem
Quote:

Originally Posted by alexmahone

$\displaystyle (-1)^a(p-1)\cdots(p-a)b!\pmod{p}$

$\displaystyle \equiv (-1)^a(p-1)!\pmod{p}$ (Note that $\displaystyle p-a = b + 1$.)

I don't understand how you got this congruence.
• Nov 30th 2011, 10:22 AM
alexmahone
Re: Wilson's Theorem
Quote:

Originally Posted by UNLVRich
I don't understand how you got this congruence.

$\displaystyle (p-1)\cdots(p-a)b!=(p-1)\cdots(p-a)(p-a-1)!=(p-1)!$
• Nov 30th 2011, 10:26 AM
UNLVRich
Re: Wilson's Theorem
Thank you!