Proving that if $p$ is a prime number then $gcd (p, (p-1)!) =1$

Question

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!

Answer 1

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

Answer 2

Your proof is correct. The only comment is that you might want to expand a bit where you say "we cannot create $p$ by multiplying the elements in $(p-1)$". Firstly, the way it is stated it is too vague. What you mean is "we cannot obtain $p$ as a product of two integers $1 < k,m < p$" but do you really understand yourself why this suffices to show that $p$ does not divide $(p-1)!$ (hint: this has a to do with $p$ being prime).