Критерий нечетности бином. коэффициентов [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!

Пусть $n$ - целое, $n>0$. Доказать, что все коэффициенты разложения бинома Ньютона $(a+b)^n$ будут нечетными тогда и только тогда, когда $n$ имеет вид $2^k-1$
Достаточность: Рассмотрим биномиальные коэффициенты $C_{2^k-1}^{p}$, где $0\leqslant p \leqslant 2^k-1$

$$C_{2^k-1}^{p}=\dfrac{(2^k-1)!}{p!(2^k-p-1)!}$$

Пусть $\alpha=v_p(n)$ - максимальная степень простого $p$ в $n$, т.е. $p^{\alpha}\mid n$, но $p^{\alpha+1}\nmid n$
Очевидно, что:

$$v_2((2^k-1)!)=\sum \limits_{r \geqslant 1}\left[\frac{2^k-1}{2^r}\right]$$

$$v_2(p!)=\sum \limits_{r \geqslant 1}\left[\frac{p}{2^r}\right]$$

$$v_2((2^k-p-1)!)=\sum \limits_{r \geqslant 1}\left[\frac{2^k-p-1}{2^r}\right]$$

Тогда:

$$v_2\left(C_{2^k-1}^{p}\right)=\sum \limits_{r \geqslant 1}\left(\left[\frac{2^k-1}{2^r}\right]-\left[\frac{p}{2^r}\right]-\left[\frac{2^k-p-1}{2^r}\right]\right)$$

Но в предыдущей теме было доказано, что член этого конечного ряда обнуляется. Значит, в биномиальных коэффициентах $C_{2^k-1}^p$, где $0\leqslant p \leqslant2^k-1$ двойка входит с нулевым показателем, т.е. биномиальные коэффициенты нечетные.
А вот как доказать необходимость я пока не придумал.
Подскажите пожалуйста.

С уважением, Whitaker.

[Chernoknizhnik]

Если я не ошибаюсь, в статье "Удивительные свойства биномиальных коэффициентов" в "Математическом просвещениее" (вот здесь http://www.mccme.ru/free-books/matprosd.html) есть это доказательство.

[chessar]

Теорема Люка Вам в помощь.

[Whitaker]

Посмотрел только, что представляет из себя теорема Люка.
Но как ее здесь использовать?

[apriv]

Нетрудно показать, что биномиальный коэффициент $C_{a+b}^a$ нечетен тогда и только тогда, когда при сложении в столбик $a$ и $b$ в двоичной системе не происходит переносов.

[chessar]

Whitaker в сообщении #630911 писал(а):

Но как ее здесь использовать?

Из неё получите критерий нечётности $C_n^k$ (при $p=2$), а далее получите из этого, условия накладываемые на $n$ при всех $k=0,1,\ldots,n$.

[Руст]

Можно обобщить для делимости коэффициентов $p|C_a^k$. Если ни один из коэффициентов $C_a^k, k=0,...,a$ не делится на р, то $a=p^n-1$ и в этом случае $C_a^k=(-1)^k\mod p^n.$

[Whitaker]

Как доказать это скажите пожалуйста?
Если $p$ - простое число и $n=n'p+n_0, k=k'p+k_0$, где $0\leqslant n_0, k_0<p$, то $C_n^k \equiv C_{n'}^{k'}C_{n_0}^{k_0} \pmod{p}$
Попытался явно написать биномиальный коэффициент и поработать с ними, но ничего умного не вышло
P.S. Здесь уже так много сказано, что я не знаю с чего именно начать.

[TOTAL]

$C_n^{k+1}/C_n^k=(n-k)/(k+1)$, поэтому $n-k$ и $k+1$ содержат одинаковую степень двойки.

[Whitaker]

TOTAL
Вы можете объяснить, что Вы написали и что Вы имеете в виду.
Извините меня, но все-таки я не телепат.

-- Вс окт 14, 2012 20:55:50 --

Скажите пожалуйста с чего вообще начать?
Мне нужно доказать необходимость.
Было дано так много советов, что непонятно с чего именно начать.

[TOTAL]

Руст в сообщении #630915 писал(а):

Можно обобщить для делимости коэффициентов $p|C_a^k$. Если ни один из коэффициентов $C_a^k, k=0,...,a$ не делится на р, то $a=p^n-1$ и в этом случае $C_a^k=(-1)^k\mod p^n.$

$C_5^a$ не делятся на 3.

-- Вс окт 14, 2012 21:58:57 --

Whitaker в сообщении #630925 писал(а):

Скажите пожалуйста с чего вообще начать?

Начните с того, что $n-k$ и $k+1$ делятся на одинаковую степень двойки.

[Руст]

Рассмотрите разложение $a=a_0+a_1p+...$ Для коэффициентов $C_a^k$. Когда $k=a_0+1$ появляется делимость на p числителя биномиального коэффициента $a(a-1)...(a-a_0)$. Чтобы биномиальный коэффициент не делился на $p$ должен быть $p|a_0+1$. Аналогично рассматривая биномиальный коэффициент с $k=a+1\mod p^i$ получаем, что $p^i|a+1$ для любого $i, p^i\le a $. Это дает $a=cp^n-1, 1\le c<p$. При этом $C_a^k=(-1)^k\mod p^n$ видно непосредственно.

[Whitaker]

TOTAL в сообщении #630928 писал(а):

Начните с того, что $n-k$ и $k+1$ делятся на одинаковую степень двойки.

Для этого наверное надо посмотреть с какой степенью входит двойка в $C_n^k$ и $C_{n}^{k+1}$?
Я так и сделал, но там получается страшное выражение

[TOTAL]

Whitaker в сообщении #630935 писал(а):

TOTAL в сообщении #630928 писал(а):

Начните с того, что $n-k$ и $k+1$ делятся на одинаковую степень двойки.

Для этого наверное надо посмотреть с какой степенью входит двойка в $C_n^k$ и $C_{n}^{k+1}$?
Я так и сделал, но там получается страшное выражение

Для этого надо вспомнить условие, согласно которому в $C_n^k$ и $C_{n}^{k+1}$ двойка входит с нулевой степенью.

TOTAL в сообщении #630923 писал(а):

$C_n^{k+1}/C_n^k=(n-k)/(k+1)$, поэтому $n-k$ и $k+1$ содержат одинаковую степень двойки.

Вам здесь что непонятно?

[ИСН]

Страшное выражение минус другое страшное выражение будет копеечка.