Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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 :)

share|improve this question
1  
The converse is also true; see Wilson's Theorem. –  hardmath Sep 4 '12 at 16:41

4 Answers 4

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.
share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.