27
$\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.

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.

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.

  • 0
    In particular, Howard, one can say that $a|(n-1)!$ and $b|(n-1)!$ by virtue of the fact that 0 and $a,b,n\in\Bbb Z$. This lets you avoid assuming the conclusion that you're trying to show.2012-06-30

7 Answers 7

0

The full proof can be found at the link below:

Wilson's theorem#Composite modulus

The answer that @WimC might (or might not) be correct in Maths. Using Combinatorics is perfectly fine (as Maths is not just Number Theory, anything can be used as long as it mathematically sound).

However, the overall proof he gave is not full, as he did not provide any proof (from first principles) why the combination ${a+b \choose a}$ is always an integer. Obviously it holds and I do not refute it. However, it needs to be proved in this context. The reason is that a proof of the combination being an integer could be taking for granted what is being asked in the original question and then using it, thus making it a "self-fulfilling prophecy". So even though it is such a succinct proof, it is actually too succinct.

The full proof of the Wikipedia article above is the most succinct it exists, as this is a very well-known/well-studied question in Maths.

PS. I did not reach 'reputation 50' so I cannot comment on other answers.

  • 0
    Yes, that's true. I do not use this StackExchange often, so I could not comment on WimC's answer. I must have '50 reputation' so I can start commenting.2018-04-10
27

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)!$.

  • 2
    @BillDubuque I ask again, Bill: In terms of combinatorics, isn't it "natural"? (I know in NT it is not trivial)2012-06-30
21

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{blue}{ab\!-\!1})=(n\!-\!1)!\,\ $ since $\rm\,\ \color{#0a0}{a\!+\!b}\le \color{blue}{ab\!-\!1} $

Note $\rm\,\color{#0A0}b\,$ divides the $\rm\color{#0A0}{green}$ term 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{#c0d}{b\!-\!1}}_{\large\ge\, 2}), \,$ true by $\rm\,a,b\ge 2,\,$ $\rm\underbrace{not\ both =2,}_{\large n\,=\,ab\,\ne\, 4}\,$ so $\,\color{#c0f}{\rm one}$ is $\,\ge 3$

That 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.

  • 3
    For a moment there I forgot I am using the color removing script, I have to say that to my color-blind eyes the colorized version looks extremely bad. My mind is too busy trying to figure out what is going on with the text and ignores the content completely (despite knowing the content from a colorless read!) you might want to consider using red and blue for future reference. Those are much harder to confuse and they sit a lot better for most color blindness. (Now I'll just turn that Greasemonkey script back on, and all will be well again...)2012-07-03
5

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.)

2

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.

2

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. 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)!$