Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Divisibility & factorial?

  1. Jun 27, 2011 #1
    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! :)
  2. jcsd
  3. Jun 27, 2011 #2
    Hi rukawakaede! :smile:

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


    What you want to show is that the multinomial coefficent


    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


    and thus


    and thus


    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


    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.
  4. Jun 27, 2011 #3
    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.
  5. Jun 27, 2011 #4
    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.
  6. Jun 27, 2011 #5
    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]?
  7. Jun 27, 2011 #6
    Hmm, I see the problem. But I made it harder than it was. In general, we know that



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

    so it is divisible by [itex]\alpha[/itex].
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Divisibility factorial
I Division Rings & Ring Homomorphisms ... A&W Corollary 2.4 ..