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$.
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.