Wilson's theorem and gcd

Question

If $n$ is composite, $gcd(n,(n−1)!+1) = 1$

I know Wilson's theorem states $(n-1)!\equiv -1 (mod $ $n)$. That gives me $(n-1)! +1 \equiv 0 (mod $ $n)$. Why is the gcd = 1?

Answer 1

We know that, if $n$ is composite and not the square of a prime, there exist positive integers $a,b,a\neq b$ such that

$$ab=n\mathrm{\ and\ } a,b<n$$

Thus, since $ab|(n-1)!$, we get that

$$n|(n-1)!$$

If $n=p^2$ with $p$ an odd prime, we have that $2p<n$, and thus

$$n|2p^2|(n-1)!$$

In either case, we get that

$$(n-1)!+1 = kn+1$$

for some positive integer $k$. We seek to find

$$\gcd(n,kn+1)$$

Assume for the sake of contradiction that this $\gcd$ is not $1$. Then there exists a prime $p$ such that

$$p|n,p|kn+1$$

$$p|kn,|kn+1$$

$$p|1$$

However, no primes divide one, and

$$\gcd(n,(n-1)!+1) = 1$$

If $n=4$, we have $\gcd(n,(n-1)!+1) = \gcd(4,7)=1$.

If $n=p$ is prime, Wilson's Theorem states that

$$(p-1)!\equiv -1\mod p$$

so $$p|(p-1)!+1$$ and $$\gcd(p,(p-1)!+1) = p$$

Answer 2

If $n$ is composite then every prime divisor $p\mid n$ satisfies $p<n$, hence $p\mid (n-1)!$. It follows that $p \nmid (n-1)!+1$. So $n$ and $(n-1)!+1$ have no primes in common.