# Prove that if $(m - 1)! + 1$ is divisible by $m$, $m$ is a prime with $(m - 1)! = 1.2.3…(m - 2)(m - 1)$

$m$ is a positive integer, and $m > 1$,
Prove that if $(m - 1)! + 1$ is divisible by $m$, $m$ is a prime.

Solve this by making a contradiction.

-
The converse is also true; see Wilson's Theorem. – hardmath Sep 4 '12 at 16:41

Let $m$ be a positive integer $> 1$. Show that if $(m-1)! + 1$ is divisible by $m$, then $m$ is a prime.

HINTS

1. Suppose, for the sake of contradiction, that $m$ is not prime. Then there is some prime $p<m$ such that $m = pk$, i.e. such that $p \mid m$.
2. Since $p \mid m$, we can say something about $p$ dividing or not dividing $(m-1)!$.
3. In general, if a number $a>1$ divides another number $b>1$, then we cannot have that $a \mid (b+1)$, as in the typical proof of the infinitude of primes.
-
I can't understand the $p<m$ such that $m=pk$, i.e. such that $p∣m$ What is the $|$ – Vchau_VN Sep 4 '12 at 15:33
Every number can be written as a product of primes. Thus if $m$ is not prime, a smaller prime divides it. – mixedmath Sep 4 '12 at 15:34
@Vchau_VN $p|m$ means "p divides m" or "m is divisible by p". – Mike Sep 4 '12 at 16:09
@Mike: Aha - I missed that he missed that part. Thanks for that! – mixedmath Sep 4 '12 at 19:45

If $m$ is not a prime, then it obviously contains some prime factor $m'$ such that $1<m'<m$. Thus $m'|(m-1)!$. Then given $m'|(m-1)!-1$, it follows that $m'|1$ which is impossible.

-

If m is not a prime, it has a prime divisor $p<m\implies p≤m-1$, hence $p\mid(m-1)!$.

But as $p\mid m$ and $m\mid((m-1)!+1)$ so, $p\mid((m-1)!+1)$

$\implies p\mid((m-1)!+1-(m-1)!)$ as $q\mid a$ and $q\mid b\implies q\mid (ax+by)$ where $a,b$ are any integers.

$\implies p\mid 1\implies m$ can not have divisor p such that $1<p≤m-1$, hence $m$ must be prime.

-
I rectified the lapsus calami. – lab bhattacharjee Sep 4 '12 at 16:37

If $m$ divides $(m-1)!+1$, there exists $k \in \mathbb{Z}$ such that $(m-1)!+1=km$ so $-(m-1)!+km=1$. From Bézout's identity, you deduce that for all $n <m$, $n$ and $m$ are relatively primes ($n$ appears in the product $(m-1)!$). So $m$ is necessarly prime.

-