2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Делимость биномиальных коэффициентов на степени простых
Сообщение13.10.2010, 13:43 
Как можно доказать, что для $ C_{5^kr}^m \vdots 5^{k+1-m} $, где $m$ - целое, $1\leqslant m \leqslant \frac{5^kr}{2}$; $r$ - положительное четное; $k$ - натуральное?
Оно же - $\frac{(5^kr-m+1)(5^kr-m+2) \cdot\cdot\cdot 5^kr}{m!}\vdots 5^{k+1-m}$
Попытался попробовать по индукции, но что-то не получилось...
З.Ы. А вообще, в общем виде, как можно доказать делимость выражения А на выражение В?

 
 
 
 Re: Делимость
Сообщение13.10.2010, 13:54 
$m\le k+1$ наверно должно быть

 
 
 
 Re: Делимость
Сообщение13.10.2010, 15:06 
Null почему? Сочетания симметричны, поэтому достаточно доказать делимость половины (Да и нужна только половина).

 
 
 
 Re: Делимость
Сообщение13.10.2010, 19:22 
Попробуйте связать $\text{ord}_p(C_{Ap+B}^{Dp})$ с $\text{ord}_p(C_{Ap}^{Dp})$ при $0 \leq B<p$, а потом $\text{ord}_p(C_{Ap}^{Dp})$ с $\text{ord}_p(C_{A}^{D})$. Можете поковыряться в $\text{ord}_p((Ap)!)$.
Должно получится.

-- Ср окт 13, 2010 20:24:00 --

Цитата:
З.Ы. А вообще, в общем виде, как можно доказать делимость выражения А на выражение В?

По-разному, в зависимости от вида $A,B$ и того, чего Вы хотите.

 
 
 
 Re: Делимость
Сообщение13.10.2010, 19:30 
lega4 в сообщении #361660 писал(а):
Null почему? Сочетания симметричны, поэтому достаточно доказать делимость половины (Да и нужна только половина).

Иначе вы проверяете делимость не на целое число.

 
 
 
 Re: Делимость
Сообщение14.10.2010, 07:37 
Null Почему? r - четное, поэтому $5^kr $можно спокойно разделить на 2.
Sonic86 эмм... Извините за глупый вопрос, но что такое ord?

 
 
 
 Re: Делимость
Сообщение14.10.2010, 07:48 
$5^{k+1-m}$ не целое

$Ord_p(n)$ - наибольшее число $l$, такое что $n\vdots p^l$

 
 
 
 Re: Делимость
Сообщение14.10.2010, 14:55 
Null ой, ошибся немного значит. Тогда так $C_{5^kr}^m \cdot 5^{5^kr-m} \vdots 5^{k+1}$, для m больших половины $5^kr$
...
Аааа, блин((( Я запутался, что же мне надо доказать(((( Вроде то, но вроде и не то.... Могу только сказать, что это отсюда post360022.html#p360022

 
 
 
 Re: Делимость
Сообщение14.10.2010, 17:40 
Ну можете просто вычислить $\text{ord}_p(C^m_{p^kr})$

 
 
 
 Re: Делимость
Сообщение15.10.2010, 08:27 
Sonic86 еще один глупый вопрос - а как его вычислять? Есть какой-то алгоритм?

 
 
 
 Re: Делимость
Сообщение15.10.2010, 17:34 
Ну Вы начните с $\text{ord}_p(n!)$, можете даже для примера $p=5$ взять. Попробуйте несколько частных случаев выписать. Или попробуйте понять, какие числа в факториале делятся на $p$, а какие - нет. Потом попробуйте получаенное выписать с помощью символа $\text{ord}_p$, ну а потом от факториалов переходите к биномиальным коэффициентам.
Делайте, пробуйте, путь немного длинный, но у Вас получится :-)

-- Пт окт 15, 2010 18:35:46 --

И алгоритм сразу найдете... Думайте, это несложно.

 
 
 
 Re: Делимость
Сообщение15.10.2010, 19:36 
Аватара пользователя
Посмотрите эту статейку:
Винберг Э. Б. Удивительные арифметические свойства биномиальных коэффициентов // Математическое просвещение. — 2008. — В. 12. — С. 33–42.
http://mi.mathnet.ru/mp237

 
 
 
 Re: Делимость
Сообщение17.10.2010, 21:58 
maxal огромное спасибо за статью! Познавательно! И как раз то, что мне нужно. Но т.к. в идеале бы не хотелось доказывать с помощью почти неизвестных теорем и фактов, почитал внимательнее, и нашел блестящее утверждение (3 страница, внизу) $C_p^l$ при $0 < l < p$ делится на$ p$. В статье написано, что это видно из определения: $C_n^k= \frac{n(n-1)(n-2)\cdot...\cdot(n-k+1)}{k!}$.
Это я один не понимаю, почему это видно из определения?

 
 
 
 Re: Делимость
Сообщение17.10.2010, 22:18 
Наверное. Подставьте туда $p$ и $l$, тогда увидите, что в числителе стоит $p$, а в знаменателе его не наблюдается.

 
 
 
 Re: Делимость
Сообщение18.10.2010, 19:30 
Joker_vD а, я что-то забыл, что p - простое :) Тогда да)))

Sonic86 Посидел сейчас - что-то не получается "нормальной" формулы даже для $\text{ord}_p(n!)$... Только в виде суммы целых частей от($n$, деленных на всевозможные степени пятерки). Т.е. что-то вроде $\left[\frac{n}{5^1}\right]+\left[\frac{n}{5^2}\right]+...+\left[\frac{n}{5^n}\right]$. Последняя степень n, конечно, утрировано, она всяко меньше, но не суть - формулы без многоточия не получается...

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group