период биномиальных коэффициентов по модулю p

[maxal]

Пусть $p$ - простое число.
Докажите, что для всякого фиксированного $k\geq 1$ период последовательности $\tbinom{0}{k}, \tbinom{1}{k}, \tbinom{2}{k}, \dots$ по модулю $p$ равен $p^\ell$, где $\ell$ - количество цифр в $p$-ичной записи $k$, т.е. $p^{\ell-1} \leq k < p^{\ell}$.

[Dendr]

Немного сумбурно, и лень везде писать строгие формулировки, но как-то так.

Введем для удобства записи функцию

$$F(m,k)=\prod\limits_{i=1}^{k}(m+i)$$

Тогда $\binom{n}{k}=\frac{F(n-k,k)}{k!}$, и доказать надо следующее свойство функции: $\forall{m, k}: F(m+p^\ell, k)p^{-K}\equiv F(m, k)p^{-K}\bmod{p}$, но если заменить $\ell$ на $\ell-1$, равенство не выполняется при бесконечном количестве $m$. Здесь $K$ - степень, с которой $p$ входит в разложение $k!$ на множители.

Пусть среди чисел $1, 2, ..., k$ имеется $r_1$ кратных $p$. Тогда среди $m+1, m+2, ..., m+k$ может быть $s_1=r_1$ (например, если $m$ кратно $p$) или $s_2=r_1+1$ кратное $p$ (если $m+1$ кратно $p$, а $k$ - нет). Больше не может, меньше - тоже.
Аналогично, для $p^2$, $s_2=r_2$ или $s_2=r_2+1$, и так далее до $s_{\ell-1}\le1$. В общем, это означает, что степень в разложении $F(m,k)$ на простые множители $p$ войдет со степенью, не меньшей $K$, и дробь сократится. Если степень больше $K$, то дробь (и биномиальный коэффициент) равны нулю по модулю $p$. Кроме того, ясно, что если в последовательности $m+1, ..., m+k$ встретится кратное $p^{\ell}$ (или даже больше - по построению такое ровно одно, обозначим его $X$), то степень $p$ обязательно превзойдет $K$, и мы получим ноль по модулю.
Добавление $m+p^\ell$, очевидно, не изменит $s_1, s_2, ..., s_{\ell-1}$. Число $X$ после добавления $p^\ell$, во всяком случае, будет кратно $p^\ell$, но необязательно более высокой степени. Но нам этого и не нужно - важно, что после сокращения в числителе все еще останутся множители $p$, и по модулю $p$ новый биномиальный коэффициент все так же сравним с нулем по модулю $p$.
Если числа $X$ нет в последовательности, а хотя бы одно $s_i=r_i+1$, то мы все так же получаем кратное $p$ в обоих случаях.
Если числа $X$ нет, и все $s_i=r_i$, то после сокращения всех $p$, все множители в $F(m+p^\ell,k)$ могут быть соотнесены со сравнимыми им по модулю $p$ множителями $F(m,k)$. Тогда обе величины равны, что и требовалось доказать: $p^\ell$ является периодом рассматриваемой последовательности.

Но возникает вопрос - может ли быть, что $p^{\ell-1}$ - тоже период?
Вернемся на пару шагов назад, и рассмотрим в ряду $m+1, .... m+k$ числа, которые кратны $p^{\ell-1}$. Обратим внимание, что добавление $m+p^{\ell-1}$ не изменяет $s_1, ... s_{\ell-1}$.
Заметим, что $X+p^{ell-1}$ не кратно $p^\ell$, то есть число $X$ "исключилось".
А если в ряду встретится число вида $m+q=(Ap-1)p^\{ell-1}$, то $m+q+p^\{ell-1}=Ap^\ell$ - кратно $p^\ell$, то есть число $X$ "появилось". Ясно, что при перемещении $m$ по числовой оси мы можем добиться того, чтобы $X$ или "перескакивало" с места на место, или "исчезало" при добавлении $m+p^\{ell-1}$ (фактически, перескакивало на область $m+k+1, ... m+p^\ell$).
Значит, будут возникать случаи, когда биномиальный коэффициент был кратен $p$, а станет некратным, и наоборот.
Таким образом, в "квазипериоде" длиной $p^{\ell-1}$ (внутри периода $p^\ell$) будут появляться и исчезать нули. Даже "батареи" нулей. Таким образом, это не период. ЧТД

[maxal]

Dendr, на мой взгляд ваше решение слишком сложно. Утверждение следует из двух: период делит $p^\ell$ и при этом $>k$.
Второе утверждение сразу следует, например, из того, что $\binom{0}k=\binom{1}k=\dots=\binom{k-1}k=0$ и $\binom{k}k=1$.

[RIP]

Можно ещё так. Возьмём свёртку Вандермонда

$$\binom{x+y}{k}=\sum_{l=0}^{k}\binom{x}{k-l}\binom{y}{l}.$$

Если $y=p^{\ell}$ и $1\leqslant l\leqslant k<p^{\ell}$, то

$$\binom{y}{l}=\frac{p^{\ell}}{l}\prod_{\lambda=1}^{l-1}\frac{p^{\ell}-\lambda}{\lambda}\equiv0\pmod{p},$$

поскольку числитель первого сомножителя (после сокращения) делится на $p$, а в остальных $p$ сокращается. Следовательно, $\binom{x+p^{\ell}}{k}\equiv\binom{x}{k}\pmod{p}$.

[maxal]

RIP, да, что-то подобное я и имел в виду. Вторую из ваших формул, кстати, проще записать в виде $\binom{p^\ell}{l} = \frac{p^\ell}l \binom{p^\ell - 1}{l-1}\equiv 0\pmod{p}$.

Ну и напрашивающееся обобщение: а каков период указанной последовательности по модулю $p^m$ для $m>1$?

[RIP]

maxal в сообщении #1593760 писал(а):

Ну и напрашивающееся обобщение: а каков период указанной последовательности по модулю $p^m$ для $m>1$?

Те же рассуждения дают $p^{\ell+m-1}$. Нужно только проверить, что $p^{\ell+m-2}$ не является периодом. Пусть $k\equiv r\pmod{p^{\ell-1}}$, $0\leqslant r<p^{\ell-1}$. Тогда из той же свёртки Вандермонда следует

$$\binom{r+p^{\ell+m-2}}{k}-\binom{r}{k}\equiv\binom{p^{\ell+m-2}}{k-r}\not\equiv0\pmod{p^{m}}.$$

Используется то, что если $1\leqslant k<p^{s}$, то

$$\nu_p\left(\binom{ap^s}{k}\right)=\nu_p\left(\frac{ap^s}{k}\prod_{i=1}^{k-1}\frac{ap^s-i}{i}\right)=\nu_p\left(\frac{ap^s}{k}\right).$$

[MGM]

Условия задачи мне мало понятны.
Как я перевел на формальный, последовательность
${s_n}\left( {p,k} \right) = \left( \begin{array}{l} n\\ k \end{array} \right)\bmod p $
a) ограничена $n<k$;
б) периодична ${s_{n + T}} = {s_n}$

Кроме того дано, что $T=p^l>k.$
То есть период больше числа элементов в последовательности. Ну или равно.
В чем ошибка моих рассуждений?

Вроде понял.n - произвольное.