PROBLEM OF THE MONTH

November 2002






Let $ n$ and $ m$ be two positive integers, with $ n\ge m$, and let $ n=\sum_{i=1}a_i2^i$ and $ m=\sum_{i=1}b_i2^i$ be their binary expansions (i.e. $ a_i$ and $ b_i$ are the digits of $ n$ and $ m$ in base $ 2$)
  1. Show that the following congruence holds

    $\displaystyle {n\choose{m}}\equiv {a_0\choose{b_0}}\cdot{a_1\choose{b_1}}\cdot{a_2\choose{b_2}}\cdots \mod 2 $

    (Here $ {n\choose{m}}$ denotes the corresponding binomial coefficient, that is the coefficient of $ x^m$ in $ (1+x)^n$. Alternatively, binomial coefficients $ {n\choose{m}}$ are sometimes denoted by the symbols $ C_n^m={}_nC_m$, usually when interpreted as the ``number of combinations of $ n$ objects taken $ m$ at a time''. By convention, $ {n\choose{m}}=0$ if $ m>n$.)
  2. Can you use the first part to say when $ {n\choose{m}}$ is odd? For what $ n$ is $ {n\choose{m}}$ odd for all $ 0\le m\le n$?
  3. Can you give a simple description of the largest power of $ 2$ dividing $ {n\choose{m}}$?