I am just making sure whether this is a valid proof:
Since $p$ is a prime number, then $p$ is only divisible by $1$ or $p$
Suppose we want to take the $gcd (p,a)$ with a, an arbitrary integer. This would result in either $p$ or $1.$
Similarly, the $gcd (p, (p-1)!)$ would be either $p$ or $1$. Note that $(p-1)! = (p-1) (p-2) … (2)(1)$
But the $gcd (p, (p-1)!)$ would not be $p$, since we cannot create p by multiplying the elements in $(p-1)$
Hence the $gcd(p, (p-1)!) = 1$ and our proof is complete.
I am wondering whether is kind of proof is valid? Any other suggestions, or way of doing this proof, so that it looks more formal or legible? Thanks!
Best Answer
You can refer to "Euclid's Lemma," which says that if the prime $p$ divides $ab$ then $p$ divides $a$ or $p$ divides $b$.
That can be readily extended (by induction, if you really want to do all the details) that if $p$ divides $a_1a_2\cdots a_m$, then $p$ divides at least one of the $a_i$.
So if $p$ divides $(p-1)!$, then $p$ divides at least one of $1,2,\dots,p-1$. This is easily seen to be impossible, since $p$ is greater than each of these.
Another way: By Wilson's Theorem, $(p-1)!\equiv -1\pmod{p}$.