2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 19:59 
Аватара пользователя


12/01/11
1320
Москва
Здравствуйте, уважаемые друзья!

Пусть $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.

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:19 


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

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:22 
Аватара пользователя


03/12/08
351
Букачача
Теорема Люка Вам в помощь.

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:29 
Аватара пользователя


12/01/11
1320
Москва
Посмотрел только, что представляет из себя теорема Люка.
Но как ее здесь использовать? :roll:

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:30 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:31 
Аватара пользователя


03/12/08
351
Букачача
Whitaker в сообщении #630911 писал(а):
Но как ее здесь использовать?
Из неё получите критерий нечётности $C_n^k$ (при $p=2$), а далее получите из этого, условия накладываемые на $n$ при всех $k=0,1,\ldots,n$.

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:34 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:41 
Аватара пользователя


12/01/11
1320
Москва
Как доказать это скажите пожалуйста?
Если $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. Здесь уже так много сказано, что я не знаю с чего именно начать.

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:52 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 20:56 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
Руст в сообщении #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$ делятся на одинаковую степень двойки.

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 21:04 
Заслуженный участник


09/02/06
4401
Москва
Рассмотрите разложение $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$ видно непосредственно.

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 21:07 
Аватара пользователя


12/01/11
1320
Москва
TOTAL в сообщении #630928 писал(а):
Начните с того, что $n-k$ и $k+1$ делятся на одинаковую степень двойки.
Для этого наверное надо посмотреть с какой степенью входит двойка в $C_n^k$ и $C_{n}^{k+1}$?
Я так и сделал, но там получается страшное выражение

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 21:12 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
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$ содержат одинаковую степень двойки.

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

 Профиль  
                  
 
 Re: Критерий нечетности бином. коэффициентов [Теория чисел]
Сообщение14.10.2012, 21:13 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Страшное выражение минус другое страшное выражение будет копеечка.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group