Биномиальные коэффициенты по модулю степени двойки

[nnosipov]

Докажите, что для $k=2^n$ числа $C_{k-1}^l$, $l=0,\,1,\,\dots,\,2^{n-1}-1$, дают попарно различные остатки при делении на $k$.

P.S. Оригинальное решение этой задачи (олимпиада 239-й школы СПб, 2002) использует индукцию по $n$. Всем желающим предлагается доказать утверждение задачи без индукции.

[Руст]

$C_{k-1}^l=\frac{(k-1)...(k-l)}{1...l}\mod k.$. Нечетные члены только меняют знак $\frac{k-i}{i}=-\mod k$.
для четных $\frac{k-2i}{2i}=\frac{k/2-i}{i}$. Соответственно $C_{k-1}^l=C_{k/2-1}^{[l/2]}(-1)^{[(l+1)/2]}$ и сводится к предыдущей степени.

[nnosipov]

Руст, условие верное ($k$ не простое, это степень двойки).

А без индукции?

[Dave]

Пусть $0 \leqslant x < y \leqslant 2^{n-1}-1$ - любые индексы одной чётности и $m$ - номер наибольшей цифры в двоичном разложении, различной у $x$ и $y$, т.е. $x=a2^{m+1}+x', \, x=a2^{m+1}+2^m+y', \; x',y' \in [0,2^m)$. Тогда $1 \leqslant m \leqslant n-2$ и между $x+1$ и $y$ включительно есть ровно одно число, делящееся на ${2^m}$, а именно $z=a2^{m+1}+2^m$. Рассмотрим равенство

$$C_{k-1}^y(x+1) \ldots z \ldots y = C_{k-1}^x(k-(x+1)) \ldots (k-z) \ldots (k-y) \eqno(1)$$

Разделим любой из сомножителей $x+1,\ldots,y$ в левой части на максимальную степень двойки, содержащуюся в нём; то же самое сделаем и с соответствующим ему множителем в правой части, учитывая, что если $d=2^rb$, где $b$ нечётное (а $r=m$ только для $d=z$ и меньше $m$ для остальных $d \in (x,y]$), то $k-d=2^n-2^rb=(2^{n-r}-b)2^r$. Допустим теперь, что $C_{k-1}^x$ и $C_{k-1}^y$ дают одинаковые остатки при делении на $2^n$. Тогда они дают и одинаковые остатки, обозначим их $c$, при делении на $p=2^{n-m+1}$. Рассмотрим (1), полученное после вышеуказанного деления на степени двойки, по модулю $p$. Как было сказано выше, каждому множителю $b$ в левой части будет соответствовать $2^{n-r}-b$ в правой, причём для всех множителей, кроме одного, будет $r \leqslant m-1$, откуда $n-r \geqslant n-m+1$ и $2^{n-r}-b \equiv -b \pmod p$. (1) перепишется так:

$$cb_1b_2 \ldots (2a+1) \ldots b_{i-1}b_i \equiv c(-b_1)(-b_2) \ldots (2^{n-m}-(2a+1)) \ldots (-b_{i-1})(-b_i) \pmod p.$$

Т.к. $x$ и $y$ одной чётности, то $i$ нечётно (если не включать частные для $z$ в ряд $b_i$). Обозначив $q=b_1b_2 \ldots b_i$, получаем:

$$cq(2a+1) \equiv -cq \left(\frac p 2 - (2a+1)\right) \pmod p.$$

$c$ и $q$ -нечётные числа, поэтому из последнего сравнения следует такое:

$$2a+1 \equiv 2a+1 - \frac p 2 \pmod p.$$

Но последнее невозможно. Полученное противоречие доказывает различие остатков от деления $C_{k-1}^x$ и $C_{k-1}^y$ на $2^n$, соответствующих $x$ и $y$ одинаковой чётности. Различие же для $x$ и $y$ разной чётности следует из того, что $C_{k-1}^x \equiv 1 \pmod 4$ при чётных $x$ и $C_{k-1}^x \equiv 3 \pmod 4$ при нечётных $x$ - это можно получить, рассматривая (1) для $y=x+1$ по модулю $4$.

[nnosipov]

Dave, спасибо. Для сравнения привожу своё решение, по существу такое же.

Нетрудно видеть, что все числа $C_{2^n-1}^m$ нечётны. Для натурального $l<m$ имеем

$$ C_{2^n-1}^m=\prod_{j=0}^{l-1}\left(\frac{2^n}{m-j}-1\right)C_{2^n-1}^{m-l}. \eqno(*) $$

Положим $m-j=2^{a_j}b_j$, где $b_j$ нечётно и $0 \leqslant a_j<n-1$. Предположим, что

$$ C_{2^n-1}^m \equiv C_{2^n-1}^{m-l} \pmod{2^n}. $$

Тогда из равенства $(*)$ будет следовать сравнение

$$ \prod_{j=0}^{l-1}\left(\frac{2^{n-a_j}}{b_j}-1\right) \equiv 1 \pmod{2^n}. $$

Покажем, что последнее невозможно. Заметим, что среди чисел $a_j$ лишь одно может быть максимальным; пусть этим числом будет $a_{j_0}$. Имеем

$$ \prod_{j=0}^{l-1}\left(\frac{2^{n-a_j}}{b_j}-1\right)= (-1)^l+(-1)^{l-1}\frac{2^{n-a_{j_0}}}{b_{j_0}}+A \equiv 1 \pmod{2^n}, $$

где $A \equiv 0 \pmod{2^{n-a_{j_0}+1}}$. Поскольку разность $n-a_{j_0}$ не меньше двух, число $l$ должно быть чётным. Но сравнение

$$ \frac{2^{n-a_{j_0}}}{b_{j_0}} \equiv A \pmod{2^n} $$

не может иметь места.

[Dave]

Да можно и так. nnosipov, Вы (и Руст) используете дроби в сравнениях по модулю. Это общепринятая нотация? Как следует понимать, к примеру, выражение $\frac{2^{n-a_{j_0}}}{b_{j_0}} \equiv A \pmod{2^n}$ ? Это означает, что число $\frac {\frac{2^{n-a_{j_0}}} {b_{j_0}} - A} {2^n}$ -целое или то, что $b_{j_0}^{-1}2^{n-a_{j_0}} \equiv A \pmod{2^n}$, где $b_{j_0}^{-1}$ - обратный вычет к $b_{j_0}$ по модулю $2^n$?

[nnosipov]

Dave в сообщении #527676 писал(а):

... или то, что $b_{j_0}^{-1}2^{n-a_{j_0}} \equiv A \pmod{2^n}$, где $b_{j_0}^{-1}$ - обратный вычет к $b_{j_0}$ по модулю $2^n$

Вот так. Не то, чтобы это было общепринято, но часто используется именно в таком смысле.

[Dave]

nnosipov в сообщении #527704 писал(а):

Dave в сообщении #527676 писал(а):

... или то, что $b_{j_0}^{-1}2^{n-a_{j_0}} \equiv A \pmod{2^n}$, где $b_{j_0}^{-1}$ - обратный вычет к $b_{j_0}$ по модулю $2^n$

Вот так. Не то, чтобы это было общепринято, но часто используется именно в таком смысле.

Понятно.

Позже пришло в голову, что в моём доказательстве можно поступить даже проще - не доказывать сравнения $C_{k-1}^x \equiv 1 \pmod 4$ и $C_{k-1}^x \equiv 3 \pmod 4$ (которые, тем не менее, верны при соответственно чётных $x<2^{n-1}$ и нечётных $x<2^{n-1}$), а с самого начала рассмотреть только чётные $x$ и $y$, но не из диапазона от $0$ до $2^{n-1}-1$, а из диапазона от $0$ до $2^{n}-1$. Тогда все вышеприведённые рассуждения справедливы, только верхняя граница для $m$ увеличится с $n-2$ до $n-1$. Получим, что остатки для всех чётных индексов различны. После этого воспользуемся равенством $C_{k-1}^x=C_{k-1}^{2^n-1-x}$, которое каждому нечётному индексу из диапазона от $0$ до $2^{n-1}-1$ включительно ставит в соответствие чётный индекс из диапазона от $2^{n-1}$ до $2^n-1$ и получим требуемое в условии различие остатков для любых индексов в диапазоне от $0$ до $2^{n-1}-1$.