Количество нечётных биномиальных коэффициентов.

[Руст]

1. Доказать, что для любого n количество нечётных биномиальных коэффициентов $C_n^k$ является степенью двойки.
2. Доказать, что для любого простого числа p и натурального n, число биномиальных коэффициентов $C_n^k$, не делящихся на р выражается формулой:

$$N=\prod_{i=1}^{p-1} (i+1)^{l_i}.$$

Выразить эти показатели через n и p.

[maxal]

Легко получается из теоремы Люка о том, что для простого $p$

$$\binom{n}{m}\equiv \binom{n_0}{m_0}\binom{n_1}{m_1}\dots \binom{n_d}{m_d}\pmod{p}$$

где $m_0, m_1, \dots, m_d$ и $n_0, n_1, \dots, n_d$ суть $p$-ичные цифры чисел $m$ и $n$, т.е. $m=m_0+m_1 p +\dots +m_d p^d$ и $n=n_0+n_1 p +\dots +n_d p^d$.

Если интересуют более глубокие результаты подобного рода - см. статью Andrew Granville "The Arithmetic Properties of Binomial Coefficients".

[Руст]

Можно проще показать, что биномиальный коэффициент $C_n^k$ не делится на p тогда и только тогда, когда все цифры числа k в p-ичном исчислении не превосходят соответствующие цифры числа n. Оттуда непосредственно получаются утверждения задачи.

[maxal]

Руст писал(а):

Можно проще показать, что биномиальный коэффициент $C_n^k$ не делится на p тогда и только тогда, когда все цифры числа k в p-ичном исчислении не превосходят соответствующие цифры числа n.

Это частный случай теоремы Люка (см. выше), которая сама по себе доказывается просто. Так что, куда уж проще?