• 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 $p=13$ and $a_1,...,a_{13}$ where $a_i\in \{1,2,...,12\}$. Given $a_1 \not 1,12$ we can find $a_2$ so that $a_1a_2 = 1$ because this is the solution to congruence. And $a_3a_4 = 1$ and so on ... until we only have $a_{10}=1$ and $a_{11}=11$. So have $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 $1+2+...+100$ he paired them like $(100+1)+(99+2)+...$ where $101$ appears $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.