• Oct 17th 2007, 02:04 PM
clockingly
The proof is:

Prove that the value of (p-1)! mod p is always p-1.

Not really sure how to approach this so any help would be greatly appreciated!
• Oct 17th 2007, 05:10 PM
ThePerfectHacker
Quote:

Originally Posted by clockingly
The proof is:

Prove that the value of (p-1)! mod p is always p-1.

Not really sure how to approach this so any help would be greatly appreciated!

This is Wilson's theorem.

The idea is to pair elements say $\displaystyle p=13$ and $\displaystyle a_1,...,a_{13}$ where $\displaystyle a_i\in \{1,2,...,12\}$. Given $\displaystyle a_1 \not 1,12$ we can find $\displaystyle a_2$ so that $\displaystyle a_1a_2 = 1$ because this is the solution to congruence. And $\displaystyle a_3a_4 = 1$ and so on ... until we only have $\displaystyle a_{10}=1$ and $\displaystyle a_{11}=11$. So have $\displaystyle a_1a_2...a_{10}a_{11} = 11$.
• Oct 18th 2007, 06:59 AM
clockingly
Thanks! So basically the proof is this?:

In order to compute (p-1)!, you have to find the product of the integers 1 through p-1. In this set of integers, there are groups of two elements (excluding the group 1 and p-1) that can be multiplied together to get a number (p-1)!/(p-1), which equals p-1, which is congruent to 1 mod p.
• Oct 18th 2007, 02:45 PM
ThePerfectHacker
Quote:

Originally Posted by clockingly
Thanks! So basically the proof is this?:

In order to compute (p-1)!, you have to find the product of the integers 1 through p-1. In this set of integers, there are groups of two elements (excluding the group 1 and p-1) that can be multiplied together to get a number (p-1)!/(p-1), which equals p-1, which is congruent to 1 mod p.

Exactly. It is like the trick Gauss did when he was a little boy when he was asked to compute $\displaystyle 1+2+...+100$ he paired them like $\displaystyle (100+1)+(99+2)+...$ where $\displaystyle 101$ appears $\displaystyle 50$ times. Now here the idea is similar except that the pairing is not as straightforward as in Gauss' trick. But however such a pairing exists. And that is what we do.