Немного сумбурно, и лень везде писать строгие формулировки, но как-то так.
Введем для удобства записи функцию
![$$F(m,k)=\prod\limits_{i=1}^{k}(m+i)$$ $$F(m,k)=\prod\limits_{i=1}^{k}(m+i)$$](https://dxdy-01.korotkov.co.uk/f/8/4/1/84134750ae078d95c9d7370c13698aaf82.png)
Тогда
![$\binom{n}{k}=\frac{F(n-k,k)}{k!}$ $\binom{n}{k}=\frac{F(n-k,k)}{k!}$](https://dxdy-02.korotkov.co.uk/f/9/d/c/9dc17c4f14c2bc666df0ebdebd1bcf6082.png)
, и доказать надо следующее свойство функции:
![$\forall{m, k}: F(m+p^\ell, k)p^{-K}\equiv F(m, k)p^{-K}\bmod{p}$ $\forall{m, k}: F(m+p^\ell, k)p^{-K}\equiv F(m, k)p^{-K}\bmod{p}$](https://dxdy-02.korotkov.co.uk/f/5/8/6/586017ec56a2e11d65dab80ffddeff0482.png)
, но если заменить
![$\ell$ $\ell$](https://dxdy-02.korotkov.co.uk/f/d/3/0/d30a65b936d8007addc9c789d5a7ae4982.png)
на
![$\ell-1$ $\ell-1$](https://dxdy-02.korotkov.co.uk/f/5/c/8/5c8c36bfb23187b84131ebca150f0b2782.png)
, равенство не выполняется при бесконечном количестве
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
. Здесь
![$K$ $K$](https://dxdy-02.korotkov.co.uk/f/d/6/3/d6328eaebbcd5c358f426dbea4bdbf7082.png)
- степень, с которой
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
входит в разложение
![$k!$ $k!$](https://dxdy-02.korotkov.co.uk/f/9/d/6/9d6c5e19ffd270ead9ea60bbae1902d082.png)
на множители.
Пусть среди чисел
![$1, 2, ..., k$ $1, 2, ..., k$](https://dxdy-01.korotkov.co.uk/f/0/b/5/0b54ec654d26fb072b0da2c417d3018382.png)
имеется
![$r_1$ $r_1$](https://dxdy-02.korotkov.co.uk/f/1/4/3/14330ec69840636094d5efd1aaa8497c82.png)
кратных
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
. Тогда среди
![$m+1, m+2, ..., m+k$ $m+1, m+2, ..., m+k$](https://dxdy-01.korotkov.co.uk/f/0/b/4/0b4efaf3365187a9956a320149bf9b5e82.png)
может быть
![$s_1=r_1$ $s_1=r_1$](https://dxdy-03.korotkov.co.uk/f/a/8/1/a814ac420793897835b7cf437567143c82.png)
(например, если
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
кратно
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
) или
![$s_2=r_1+1$ $s_2=r_1+1$](https://dxdy-03.korotkov.co.uk/f/6/7/5/6750824fca3c09d30fdac5cb4ef9f9c082.png)
кратное
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
(если
![$m+1$ $m+1$](https://dxdy-01.korotkov.co.uk/f/4/6/8/468c63cefe623320eeebfe059e5f840882.png)
кратно
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, а
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
- нет). Больше не может, меньше - тоже.
Аналогично, для
![$p^2$ $p^2$](https://dxdy-04.korotkov.co.uk/f/3/6/7/367612346bbcbb202f19d739190c1a9982.png)
,
![$s_2=r_2$ $s_2=r_2$](https://dxdy-02.korotkov.co.uk/f/1/b/e/1beafa4d0fa20655cabf5e18010437b982.png)
или
![$s_2=r_2+1$ $s_2=r_2+1$](https://dxdy-03.korotkov.co.uk/f/6/b/a/6ba0dffe32cde66f4d414d9c28588dfb82.png)
, и так далее до
![$s_{\ell-1}\le1$ $s_{\ell-1}\le1$](https://dxdy-03.korotkov.co.uk/f/6/2/1/6215e9dd164bb1ee00fcba2bc02e507482.png)
. В общем, это означает, что степень в разложении
![$F(m,k)$ $F(m,k)$](https://dxdy-01.korotkov.co.uk/f/c/a/8/ca8ad42fc2881c04141f0465858d150382.png)
на простые множители
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
войдет со степенью, не меньшей
![$K$ $K$](https://dxdy-02.korotkov.co.uk/f/d/6/3/d6328eaebbcd5c358f426dbea4bdbf7082.png)
, и дробь сократится. Если степень больше
![$K$ $K$](https://dxdy-02.korotkov.co.uk/f/d/6/3/d6328eaebbcd5c358f426dbea4bdbf7082.png)
, то дробь (и биномиальный коэффициент) равны нулю по модулю
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
. Кроме того, ясно, что если в последовательности
![$m+1, ..., m+k$ $m+1, ..., m+k$](https://dxdy-03.korotkov.co.uk/f/e/d/a/eda29cf3dc232d6b627c9044551e72cb82.png)
встретится кратное
![$p^{\ell}$ $p^{\ell}$](https://dxdy-02.korotkov.co.uk/f/9/6/c/96c7587fa6abd27791be01ebc399fdec82.png)
(или даже больше - по построению такое ровно одно, обозначим его
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
), то степень
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
обязательно превзойдет
![$K$ $K$](https://dxdy-02.korotkov.co.uk/f/d/6/3/d6328eaebbcd5c358f426dbea4bdbf7082.png)
, и мы получим ноль по модулю.
Добавление
![$m+p^\ell$ $m+p^\ell$](https://dxdy-04.korotkov.co.uk/f/b/b/5/bb5a81a4f786ec5e9901e8b7366d288782.png)
, очевидно, не изменит
![$s_1, s_2, ..., s_{\ell-1}$ $s_1, s_2, ..., s_{\ell-1}$](https://dxdy-01.korotkov.co.uk/f/4/5/1/451dcd7fdad876ab3185fbeb21898bf082.png)
. Число
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
после добавления
![$p^\ell$ $p^\ell$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df85c27843ac1ce3258ce8ea846c88d382.png)
, во всяком случае, будет кратно
![$p^\ell$ $p^\ell$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df85c27843ac1ce3258ce8ea846c88d382.png)
, но необязательно более высокой степени. Но нам этого и не нужно - важно, что после сокращения в числителе все еще останутся множители
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, и по модулю
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
новый биномиальный коэффициент все так же сравним с нулем по модулю
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
.
Если числа
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
нет в последовательности, а хотя бы одно
![$s_i=r_i+1$ $s_i=r_i+1$](https://dxdy-03.korotkov.co.uk/f/a/f/2/af25b324c4a23187cc7aecb98e8a0d4082.png)
, то мы все так же получаем кратное
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
в обоих случаях.
Если числа
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
нет, и все
![$s_i=r_i$ $s_i=r_i$](https://dxdy-04.korotkov.co.uk/f/3/0/5/305ad6e9bbb9ffa3c2a5de3ec2b2852a82.png)
, то после сокращения всех
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, все множители в
![$F(m+p^\ell,k)$ $F(m+p^\ell,k)$](https://dxdy-03.korotkov.co.uk/f/2/b/5/2b5a43aea824330da2e6fec4b4126f7182.png)
могут быть соотнесены со сравнимыми им по модулю
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
множителями
![$F(m,k)$ $F(m,k)$](https://dxdy-01.korotkov.co.uk/f/c/a/8/ca8ad42fc2881c04141f0465858d150382.png)
. Тогда обе величины равны, что и требовалось доказать:
![$p^\ell$ $p^\ell$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df85c27843ac1ce3258ce8ea846c88d382.png)
является периодом рассматриваемой последовательности.
Но возникает вопрос - может ли быть, что
![$p^{\ell-1}$ $p^{\ell-1}$](https://dxdy-01.korotkov.co.uk/f/8/5/2/852703adb2883897b945854cf6c10b6a82.png)
- тоже период?
Вернемся на пару шагов назад, и рассмотрим в ряду
![$m+1, .... m+k$ $m+1, .... m+k$](https://dxdy-02.korotkov.co.uk/f/9/a/f/9aff80976db8f24526637257a04274d482.png)
числа, которые кратны
![$p^{\ell-1}$ $p^{\ell-1}$](https://dxdy-01.korotkov.co.uk/f/8/5/2/852703adb2883897b945854cf6c10b6a82.png)
. Обратим внимание, что добавление
![$m+p^{\ell-1}$ $m+p^{\ell-1}$](https://dxdy-01.korotkov.co.uk/f/c/a/1/ca1b1e101720e2fb8ab896024842b19882.png)
не изменяет
![$s_1, ... s_{\ell-1}$ $s_1, ... s_{\ell-1}$](https://dxdy-04.korotkov.co.uk/f/f/5/7/f574ca6bd3f83b78846c4060e8172acd82.png)
.
Заметим, что
![$X+p^{ell-1}$ $X+p^{ell-1}$](https://dxdy-04.korotkov.co.uk/f/f/5/2/f526f0919a489bcb14adaa6a0ca1734f82.png)
не кратно
![$p^\ell$ $p^\ell$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df85c27843ac1ce3258ce8ea846c88d382.png)
, то есть число
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
"исключилось".
А если в ряду встретится число вида
![$m+q=(Ap-1)p^\{ell-1}$ $m+q=(Ap-1)p^\{ell-1}$](https://dxdy-02.korotkov.co.uk/f/1/4/7/1475fedbb7de1e78c01b74ce0b21bb6c82.png)
, то
![$m+q+p^\{ell-1}=Ap^\ell$ $m+q+p^\{ell-1}=Ap^\ell$](https://dxdy-02.korotkov.co.uk/f/d/8/0/d8020e19897b9068bdac274adf6b742e82.png)
- кратно
![$p^\ell$ $p^\ell$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df85c27843ac1ce3258ce8ea846c88d382.png)
, то есть число
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
"появилось". Ясно, что при перемещении
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
по числовой оси мы можем добиться того, чтобы
![$X$ $X$](https://dxdy-01.korotkov.co.uk/f/c/b/f/cbfb1b2a33b28eab8a3e59464768e81082.png)
или "перескакивало" с места на место, или "исчезало" при добавлении
![$m+p^\{ell-1}$ $m+p^\{ell-1}$](https://dxdy-04.korotkov.co.uk/f/b/0/9/b097acd1a46626f2b457e87bd15e4ade82.png)
(фактически, перескакивало на область
![$m+k+1, ... m+p^\ell$ $m+k+1, ... m+p^\ell$](https://dxdy-01.korotkov.co.uk/f/4/9/9/499e75752bd92ef08361f8f7f0469f0a82.png)
).
Значит, будут возникать случаи, когда биномиальный коэффициент был кратен
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, а станет некратным, и наоборот.
Таким образом, в "квазипериоде" длиной
![$p^{\ell-1}$ $p^{\ell-1}$](https://dxdy-01.korotkov.co.uk/f/8/5/2/852703adb2883897b945854cf6c10b6a82.png)
(внутри периода
![$p^\ell$ $p^\ell$](https://dxdy-02.korotkov.co.uk/f/d/f/8/df85c27843ac1ce3258ce8ea846c88d382.png)
) будут появляться и исчезать нули. Даже "батареи" нулей. Таким образом, это не период. ЧТД