2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Делимость
Сообщение01.03.2014, 10:24 
Заслуженный участник


09/02/06
4382
Москва
Докажите, что для любого натурального n, сумма
$$S(n)=\sum_{d|n}\mu(\frac{n}{d})\binom{4d}{d}$$
делится на $n^3$.

 Профиль  
                  
 
 Re: Делимость
Сообщение01.03.2014, 16:31 
Заслуженный участник


08/04/08
8556
$4$ и $1$ тут не причем, можно доказывать, что для любых $a,b$
$$S(n)=\sum\limits_{d|n}\mu\left(\frac{n}{d}\right)\binom{ad}{bd}\equiv 0\pmod{n^3}$$
Это следует из соотношения
$$\binom{ap^k}{bp^k}\equiv\binom{ap^{k-1}}{bp^{k-1}}\pmod{p^{3k}} \eqno{(B)}$$
Действительно, если $(B)$ верно и $p^k||n$, то
$$S(n)=
\sum\limits_{d|n, p|\frac{n}{d}}\mu\left(\frac{n}{d}\right)\binom{ad}{bd}+
\sum\limits_{d|n, p\nmid \frac{n}{d}}\mu\left(\frac{n}{d}\right)\binom{ad}{bd}
=$$
$$
\pm\sum\limits_{d|n}\mu\left(\frac{n}{d}\right)\binom{adp^{k-1}}{bdp^{k-1}}
\mp\sum\limits_{d|n}\mu\left(\frac{n}{d}\right)\binom{adp^k}{bdp^k}
\equiv 0\pmod{p^{3k}}$$
В левой части $(B)$ выделим и сгруппируем множители, кратные $p$. Сократим их - получится $\binom{ap^{k-1}}{bp^{k-1}}$. Обозначим $M=\{j:1\leqslant j\leqslant bp^k, p\nmid j\}$. Тогда
$$(B)\Leftrightarrow
\dfrac{\prod\limits_{j\in M}(ap^k-j)}{\prod\limits_{j\in M}j}
\equiv1\pmod{p^{3k}}\Leftrightarrow
\prod\limits_{j\in M}\left(\frac{ap^k}{j}-1\right)
\equiv1\pmod{p^{3k}}\Leftrightarrow
$$
$$1-bp^k\sum\limits_{j\in M}\frac{1}{j}
+(bp^k)^2\sum\limits_{i<j,i,j\in M}\frac{1}{ij}\equiv1\pmod{p^{3k}}\Leftrightarrow
\sum\limits_{j\in M}\frac{1}{j}\equiv 0\pmod{p^{2k}}, \ \ \ 
\sum\limits_{i<j,i,j\in M}\frac{1}{ij}\equiv 01\pmod{p^{k}}$$
Обозначим $K=\{j:1\leqslant j\leqslant p^k, p\nmid j\}$. Тогда
$$\sum\limits_{i<j,i,j\in M}\frac{1}{ij}\equiv 0\pmod{p^{k}}\Leftrightarrow
b\sum\limits_{i<j,i,j\in K}\frac{1}{ij}\equiv 0\pmod{p^{k}}$$
Используем то, что $j\to gj$ - биекция на $\mathbb{Z}_{p^k}^{\times}$:
$$\sum\limits_{i<j,i,j\in K}\frac{1}{ij}\equiv g^{-2}\sum\limits_{i<j,i,j\in K}\frac{1}{ij}\equiv 0\pmod{p^{k}}$$
Далее
$(p^n+j)^{-1}\equiv j^{-1}(1+j^{-1}p^n)^{-1}\equiv j^{-1}-j^{-2}p^n$
Значит
$$\sum\limits_{j\in M}j^{-1}\equiv 
\sum\limits_{j\in K}j^{-1}+Cp^n\sum\limits_{j\in K}j^{-2}\equiv 
0\pmod{p^{2k}}$$
2-я сумма $\sum\limits_{j\in K}j^{-2}\equiv 0\pmod{p^{k}}$ (снова используем биекцию $j\to gj$).
Остается доказать, что
$$\sum\limits_{j=1,p\nmid j}^{p^k}j^{-1}\equiv 0\pmod{p^{2k}}$$
Используем прием из статьи Винберга в Матпросвещении:
$$2\sum\limits_{j\in K}\frac{1}{j}\equiv 
\sum\limits_{j\in K}\frac{1}{j}+\sum\limits_{j\in K}\frac{1}{p^k-j}\equiv p^k\sum\limits_{j\in K}\frac{1}{j^2} \equiv 0\pmod{p^{2k}}$$
Все.
Длинно, муторно, но работает. Заодно хорошее обобщение т.Вольстенхольма получили.

 Профиль  
                  
 
 Re: Делимость
Сообщение01.03.2014, 16:53 
Заслуженный участник


09/02/06
4382
Москва
Sonic86 в сообщении #831722 писал(а):
$4$ и $1$ тут не причем, можно доказывать, что для любых $a,b$
$$S(n)=\sum\limits_{d|n}\mu\left(\frac{n}{d}\right)\binom{ad}{bd}\equiv 0\pmod{n^3}$$
Это следует из соотношения
$$\binom{ap^k}{bp^k}\equiv\binom{ap^{k-1}}{bp^{k-1}}\pmod{p^{3k}} \eqno{(B)}$$

Для любых $a,b$ это неверно. Верно только $n^3|6S(n)$.
Мешает этому простые числа 2 и 3, для которых соотношение (B) может не выполняться.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

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



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

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


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

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