5
$\begingroup$

$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.
My english isn't so well. Please help and thank you for your attention :)

  • 1
    The converse is also true; see [Wilson's Theorem](http://en.wikipedia.org/wiki/Wilson's_theorem).2012-09-04

4 Answers 4

5

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 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.
  • 0
    @Mike: Aha - I missed that he missed that part. Thanks for that!2012-09-04
4

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

2

If m is not a prime, it has a prime divisor $p, 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, hence $m$ must be prime.

  • 0
    I rectified the lapsus calami.2012-09-04
1

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 , $n$ and $m$ are relatively primes ($n$ appears in the product $(m-1)!$). So $m$ is necessarly prime.