Results 1 to 2 of 2

Thread: Binomial coefficient

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,115
    Thanks
    7

    Binomial coefficient

    Let $\displaystyle p\geq3$ be a prime number, and let m and $\displaystyle k<p^m$ be positive integers. Show that $\displaystyle \dbinom{p^m}{k}$ is divisible by p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148

    Re: Binomial coefficient

    Quote Originally Posted by alexmahone View Post
    Let $\displaystyle p\geq3$ be a prime number, and let m and $\displaystyle k<p^m$ be positive integers. Show that $\displaystyle \dbinom{p^m}{k}$ is divisible by p.
    We have the simple identity $\displaystyle \binom{p^m}{k}=\binom{p^m-1}{k-1}\cdot\frac{p^m}{k}$ for $\displaystyle 0<k$. Hence, (a)$\displaystyle k\cdot\binom{p^m}{k}=\binom{p^m-1}{k-1}\cdot p^m$.

    Let $\displaystyle p^j$ be the largest power of $\displaystyle p$ that divides $\displaystyle k$. So $\displaystyle \frac{k}{p^j}\cdot\binom{p^m}{k}=\binom{p^m-1}{k-1}\cdot p^{m-j}$, by (a).

    From $\displaystyle p^j\leq k<p^m$ it follows that $\displaystyle m-j>0$ and so $\displaystyle p$ divides $\displaystyle \frac{k}{p^j}\cdot\binom{p^m}{k}$, where $\displaystyle p$ does not divide $\displaystyle \frac{k}{p^j}$. Euclid's Lemma implies then that $\displaystyle p$ must divide $\displaystyle \binom{p^m}{k}$.


    By the way, the argument works for $\displaystyle p=2$ also.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binomial Coefficient
    Posted in the Math Challenge Problems Forum
    Replies: 5
    Last Post: Aug 15th 2010, 08:50 AM
  2. binomial coefficient.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 12th 2010, 10:30 PM
  3. Binomial Coefficient
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 1st 2009, 05:37 PM
  4. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Oct 2nd 2009, 01:06 PM
  5. Binomial Coefficient
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Oct 27th 2007, 04:35 AM

Search Tags


/mathhelpforum @mathhelpforum