Делимость

[Руст]

Докажите, что для любого натурального n, сумма

$$S(n)=\sum_{d|n}\mu(\frac{n}{d})\binom{4d}{d}$$

делится на $n^3$.

[Sonic86]

$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}}$$

Все.
Длинно, муторно, но работает. Заодно хорошее обобщение т.Вольстенхольма получили.

[Руст]

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) может не выполняться.