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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Divisibility & factorial?
  1. Synthetic division (Replies: 2)

  2. Divisibility question (Replies: 12)

  3. Divisibility Question (Replies: 6)

  4. Division ring (Replies: 0)

Loading...