Divisibility & factorial?

  • #1

Main Question or Discussion Point

Hi, we know that for all interger [itex]m[/itex], [itex]n_1!\cdots n_k![/itex] divides [itex]m![/itex] where [itex]n_1+\cdots+n_k=m[/itex].

Now I want to show that [itex]m! (n!)^m[/itex] divides [itex](mn)![/itex].

We see that [itex](n!)^m[/itex] divides [itex](mn)![/itex] since [itex]\overbrace{n+\cdots+n}^{m-terms}=mn[/itex]

Also [itex]m!(nm-m)![/itex] divides [itex](mn)![/itex] similarly.

But how could I show my required statement above? It works for some examples that I've tested and I believe it is true.

Any inputs would be appreciated! :)
 

Answers and Replies

  • #2
22,097
3,282
Hi rukawakaede! :smile:

First of all, let us define the multinomial coefficient: (for [itex]k_1+...+k_m=1[/itex])

[tex]\binom{n}{k_1,...,k_m}=\frac{n!}{k_1!...k_m!}[/tex]

What you want to show is that the multinomial coefficent

[tex]\binom{nm}{n,...,n}[/tex]

is divisible by m!

Now, first note the following equality that represents the multinomial coefficients as binomials:

[tex]\binom{nm}{n,...,n}=\binom{n}{n} \binom{2n}{n}\binom{3n}{n} ...\binom{mn}{n}[/tex]

So it actually suffices to show that [itex]\binom{kn}{n}[/itex] is divisible by k.

Let me give the idea on how to prove this by showing that 2 divides [itex]\binom{2n}{n}[/itex].

Factorize [itex]2n=2^rs[/itex] such that 2 does not divide s. In modulo 2, we know that

[tex](X+1)^2=X^2+1[/tex]

and thus

[tex](X+1)^{2^r}=X^{2^r}+1[/tex]

and thus

[tex](X+1)^{2n}=(X^{2^r}+1)^s[/tex]

Expanding both terms using the binomial theorem gives us that the coefficient of [itex]X^n[/itex] in both terms are equal. But the coefficient of [itex]X^n[/itex] in the left polynomial is

[tex]\binom{2n}{n}[/tex]

But the coefficient of [itex]X^n[/itex] in the right polynomial is 0, as we can never write [itex]n=2^rk[/itex] (we have a 2 too much).

Hope that helped.
 
  • #3
218
0
I'm wondering how you would generalize this method to composite m. The identity [itex](1 + x)^{m} \equiv 1 + x^m[/itex] doesn't hold for composite bases.
 
  • #4
22,097
3,282
I'm wondering how you would generalize this method to composite m. The identity [itex](1 + x)^{m} \equiv 1 + x^m[/itex] doesn't hold for composite bases.
Prove it for all the prime factors. For example, to show that something is divisible by 6 is equivalent to showing that it is divisible by 2 and 3.
 
  • #5
218
0
Prove it for all the prime factors. For example, to show that something is divisible by 6 is equivalent to showing that it is divisible by 2 and 3.
The problem I'm having is with prime powers. For example, your method proves 2 divides [itex]\binom{2n}{n}[/itex]. Can you give an example on how you would prove, say, [itex]\binom{8n}{n}[/itex]?
 
  • #6
22,097
3,282
Hmm, I see the problem. But I made it harder than it was. In general, we know that

[tex]\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}[/tex]

Thus

[tex]\binom{\alpha n}{n}=\alpha\binom{\alpha n-1}{n-1}[/tex]

so it is divisible by [itex]\alpha[/itex].
 

Related Threads on Divisibility & factorial?

  • Last Post
Replies
1
Views
2K
Replies
9
Views
3K
  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
7
Views
6K
  • Last Post
Replies
17
Views
9K
  • Last Post
Replies
9
Views
7K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
26K
Top