30
$\begingroup$

I have a proof and need some feedback. It seems really obvious that the statement is true but it is always the obvious ones that are a little trickier to prove. So I would appreciate any feedback. Thank you!

Here is what I am asked to prove:

If $n$ is composite then $(n-1)! \equiv 0 \pmod n$.

Proof:

$n$ is composite $\implies n=ab$ where $a,b \in \mathbb{Z}$ and $0<a,b<n$.

Case 1: If $a=b$ then $n=a^{2}$. Now $n \mid (n-1)! \implies a \mid (n-1)!$, so $$\begin{aligned} (n-1)! &\equiv 1\times 2\times \dotsb \times a \times\dotsb\times (n-a)\times\dotsb\times (n-1) \\ &\equiv 1\times 2\times \dotsb\times a \times\dotsb\times -a\times\dotsb\times -1 \\ &\equiv 0 \pmod n \end{aligned}$$

Case 2: $0<a<b<n$.

Then, since $a \mid n$, $b \mid n$ and $n \mid (n-1)!$ we have that $a \mid (n-1)!$ and $b \mid (n-1)!$.

So this implies $(n-1)! \equiv 1\times 2\times \dotsb\times a \times\dotsb\times b\times\dotsb\times (n-1) \equiv 0 \pmod n$, Q.E.D.

$\endgroup$
9
  • $\begingroup$ In case 1, there is a subcase where $a=n-a$, and the result is false. $\endgroup$ – Jonas Meyer Jun 30 '12 at 8:32
  • 11
    $\begingroup$ $3!\equiv2\pmod4$ $\endgroup$ – Mike Jun 30 '12 at 8:39
  • $\begingroup$ @JonasMeyer I did not consider that case. Darn, this also only happens when n=4. :( thank you. $\endgroup$ – HowardRoark Jun 30 '12 at 8:41
  • $\begingroup$ @HowardRoark: Exactly (and Mike has also made it explicit). What is the source of the problem? Was the exception of $n=4$ not mentioned? Otherwise, your method looks good. $\endgroup$ – Jonas Meyer Jun 30 '12 at 8:42
  • $\begingroup$ @JonasMeyer This is how the question goes: (a)calculate $(n-1)!$(mod $n$) for $n=10,12,14,$ and $15$. (b) guess a theorem and prove it. $\endgroup$ – HowardRoark Jun 30 '12 at 8:46
25
$\begingroup$

Hint $\rm\ n\, =\, \color{#C00}a\:\!\color{#0A0}b\mid1\!\cdot\! 2\cdots\color{#C00} a\:\color{#0A0}{(a\!+\!1)\, (a\!+\!2) \cdots (a\!+\!b)}\cdots (\color{#90f}{ab\!-\!1})=(n\!-\!1)!\,\ $ by $\rm\,\ \color{#0a0}{a\!+\!b}\le \color{#90f}{ab\!-\!1} $

Note $\rm\,\color{#0A0}b\,$ divides $\rm\color{#0A0}{green}$ product since a sequence of $\rm\,b\,$ consecutive integers has a multiple of $\rm\,b,\,$

and $\rm\,a\!+\!b \le ab\!-\!1 \!\!\iff\!\! 2\le (\underbrace{a\!-\!1}_{\large \ge\,1})(\underbrace{\color{#f70}{b\!-\!1}}_{\large\color{#f70}{\ge\, 2}}), \,$ true by $\rm\,a,b\ge 2,\,$ $\rm\underbrace{not\ both\!=\!2,}_{\large n\,=\,ab\,\ne\, 4}\,$ so $\,\color{#f70}{\rm one}$ is $\,\color{#f70}{\ge 3}$

The prior inequality implies that all of the $\rm\color{#0A0}{green}$ factors do occur in $\rm\,(ab\!-\!1)!$

Note $ $ That $\rm\:\color{#0A0}b\:$ divides the above $\rm\color{#0A0}{green}$ term is not deduced from the fact that it is divisible by $\rm\,b!\,$ by integrality of the binomial coefficient $\rm\:(a\!+\!b:a),\:$ as in WimC's answer. Rather, we deduce it from the more elementary fact that a sequence of $\rm\,b\,$ consecutive integers contains a multiple of $\rm\,b,\,$ which is an immediate consequence of (Euclidean) division.

$\endgroup$
0
30
$\begingroup$

If $n > 4$ and $n = a \cdot b$ with $a, b \geq 2$ then $a + b \leq n - 1$. Since ${a+b \choose a}$ is an integer it follows that $n = a \cdot b \mid a! \cdot b! \mid (a + b)! \mid (n - 1)!$.

$\endgroup$
4
  • $\begingroup$ @TMM Binomial coefficients are a bit of a sledgehammer here. Instead, more simply, one needs only that every sequence of consecutive integers of length $\rm\:b\:$ contains a multiple of $\rm\:b.\:$ See my answer. $\endgroup$ – Bill Dubuque Jun 30 '12 at 14:33
  • $\begingroup$ @BillDubuque Why do you consider it is a sledgehammer? Maybe it is true from a number theoretical view, but very straightforward from a combinatorial one, right? $\endgroup$ – Pedro Tamaroff Jun 30 '12 at 15:28
  • $\begingroup$ @Peter Integrality of binomial coefficients is a much deeper result than said divisibility result. See the note I added to my answer. $\endgroup$ – Bill Dubuque Jun 30 '12 at 15:57
  • 2
    $\begingroup$ @BillDubuque I ask again, Bill: In terms of combinatorics, isn't it "natural"? (I know in NT it is not trivial) $\endgroup$ – Pedro Tamaroff Jun 30 '12 at 16:37
6
$\begingroup$

Recall the definition of the factorial: $$m! = \prod_{k=1}^m k = 1 \times 2 \times 3 \times \dotsb \times m.$$

From this is should be obvious that $ab \mid m!$ for any $1 \le a < b \le m$, since both $a$ and $b$ appear as distinct terms in the product.

In particular, let $n$ be a composite number, and let $m = n-1$. If $n$ is not the square of a prime, there exist two distinct integers $1 < a < b < n$ such that $n = ab$ (you may want to prove this — it's not difficult), and thus $n \mid (n-1)!$.

What if $n$ is the square of a prime, i.e. $n = p^2$ for some prime $p$? If $p = 2$, we have a counterexample: $4 \nmid 3! = 6$.

However, if $p > 2$, then $2p < p^2 = n$, and thus we may choose $a = p$ and $b = 2p$ to show that $2n \mid (n-1)!$, and therefore also that $n \mid (n-1)!$.

Finally, the fact that the result does not hold for any prime $n$ follows easily from the fundamental theorem of arithmetic, as the prime factorization of $(n-1)!$ will not contain $n$ if it is prime. (I'm sure there are weaker lemmas that could be used to prove this, but why bother? The FToA does it cleanly and easily.) Thus, for integers $n > 1$, $n \nmid (n-1)!$ if and only if $n$ is either prime or $4$.

(In fact, the result holds trivially for $n = 1$ too, at least under the usual definition of $0! = 1$, but that does not follow from the argument above — $1$ is not composite in the sense needed for the argument.)

$\endgroup$
3
  • $\begingroup$ Ps. See also Wilson's theorem, which says that $(n-1)! \equiv -1 \pmod n$ if and only if $n$ is prime. $\endgroup$ – Ilmari Karonen Dec 13 '15 at 19:14
  • $\begingroup$ I got the part why prime numbers dont satisfy this but How choosing $a=2p$ and $b=p$ proves it for all composite number,i think you have assumed $ab|(n-1)!$ first then you choose a,b and therefore$ab=2p^2|(n-1)!$ and using $n=ab$ you conclude $2n|(n-1)!$ how is that a proof ? Please correct me if i am getting you wrong. $\endgroup$ – NewBornMATH Mar 24 '19 at 15:40
  • 1
    $\begingroup$ @NewBornMATH: There are four distinct cases that I consider above: a) $n$ is prime, b) $n=4=2^2$, c) $n$ is the square of some prime $p>2$, and d) $n$ is neither a prime nor the square of a prime. In cases a and b, $n$ does not divide $(n-1)!$. In case c, we have $1<p<2p<n$, and thus $p(2p)=2p^2=2n$ divides $(n-1)!$. In case d, which I consider in the third paragraph above, $n$ has a pair of integer divisors $a$ and $b = n/a$ such that $1<a<\sqrt n<b<n$ (I have omitted the proof of this, but it's not hard to show by contradiction), and thus $n=ab$ divides $(n-1)!$. $\endgroup$ – Ilmari Karonen Mar 25 '19 at 5:40
2
$\begingroup$

Since $n|(n-1)!$ and $(n-1)!\equiv0\pmod n$ are equivalent, if you can prove one, you should be done.

Take your case 2 for example. You say "then since $a|n,b|n$, and $n|(n-1)!$..." But $n|(n-1)!$ is what you set out to prove and you weren't explicit about why it's true, which is the point of a proof in the first place.

What I think you were going for is that $(n-1)!$ is the product of all positive integers $\le n-1$, which includes $a$ and $b$. Change the order of multiplication and let the product of all integers $\le n-1$ excluding $a$ and $b$ be equal to a new constant $k$. So $(n-1)!=kab=kn$. Therefore, $n|(n-1)!$ or $(n-1)!\equiv0\pmod n$.

Case 1 was a bit more explicit, but you tried using your conclusion to try to prove something else again. And you missed the loophole that Jonas's comment points out. You may want to be a bit more explicit about why the product is zero as well rather than just stating that it is.

$\endgroup$
2
$\begingroup$

We will assume that $n>4$, since $4\hspace{-3pt}\not|\,3!$.

Let $p$ be the smallest factor of $n$. Since $n$ is composite, $p\le\sqrt{n}$.

If $p=\sqrt{n}$, then since $n>4$, we must have $p>2$ so that $2p<p^2=n$. Thus, $p\le n-1$ and $2p\le n-1$, and therefore, $2n=p\cdot2p\,|\,(n-1)!$

If $p<\sqrt{n}$, then $n/p>\sqrt{n}$. Thus, $p\le n-1$ and $n/p\le n-1$, and therefore, $n=p\cdot n/p\,|\,(n-1)!$

In either case, $n|(n-1)!$

$\endgroup$
0
$\begingroup$

(THIS IS ELEMENTARY PROOF)

If n is composite, then n is the product of two numbers smaller than n. (Those in turn might be prime or not prime, it doesn't matter).

For any case other than a perfect square of a prime, you can find two numbers which are different from each other.

For example for 60, 3 * 20 or 4 * 15 or other choices. But there will always be at least one.

Both of those numbers appear in (n-1)!, so n divides (n-1)!

If n IS the square of a prime p, then the only divisors are p and p (again). (E.g. 49 = 7 * 7)

But if p > 2, then 2p is divisible by p and 2p < n, so (n-1)! is divisible by p², which is n. (E.g. n = 9, 3 divides 3, and 3 divides 6, so 3 divides 8!)

The only exception to this is 4 = 2*2. 3! = 6, which is not divisible by 4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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