... Интересен также вопрос делимости членов указанных последовательностей, но этим пока не занимался.
В случае
![$k=1$ $k=1$](https://dxdy-04.korotkov.co.uk/f/7/e/b/7eb22be4bf74527b54b6d6093847814782.png)
возможен единственный простой делитель
![$p=2$ $p=2$](https://dxdy-02.korotkov.co.uk/f/9/0/2/90264925fb137831c8f410cd14c75cff82.png)
. Случай
![$k=2$ $k=2$](https://dxdy-03.korotkov.co.uk/f/e/0/2/e021cb770c745ec45faa5ae82936a9b882.png)
описан подробно в литературе, но для
![$k>2$ $k>2$](https://dxdy-03.korotkov.co.uk/f/a/5/f/a5f6f1052ef59b00868159d9d1a605c982.png)
простых закономерностей на первый взгляд не просматривается. Будем выписывать вместо
![$F_n^k$ $F_n^k$](https://dxdy-03.korotkov.co.uk/f/e/2/2/e22fc375f7327d18c6552bee97e445f482.png)
остатки деления
![$F_n^k \mod p$ $F_n^k \mod p$](https://dxdy-01.korotkov.co.uk/f/c/c/f/ccf71899541c70e6e255309f5bb56f3382.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)
конечно, и с некоторого
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
неизбежно повторение. Значит последовательность
![$F_n^k \mod p$ $F_n^k \mod p$](https://dxdy-01.korotkov.co.uk/f/c/c/f/ccf71899541c70e6e255309f5bb56f3382.png)
периодична (
![$F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$ $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$](https://dxdy-02.korotkov.co.uk/f/1/a/4/1a4b2f04da1f28e3a9da9ed746e60baf82.png)
), причем для фиксированных
![$k,p$ $k,p$](https://dxdy-02.korotkov.co.uk/f/9/5/a/95aec30bdd5d9cf859651636234357c982.png)
длина периода определена однозначно. Обозначим
![$N_p^k$ $N_p^k$](https://dxdy-03.korotkov.co.uk/f/2/2/7/22739a508f798d5cf1a3d1b0cc80dc8482.png)
– длина периода последовательности
![$F_n^k \mod p$ $F_n^k \mod p$](https://dxdy-01.korotkov.co.uk/f/c/c/f/ccf71899541c70e6e255309f5bb56f3382.png)
. Отсюда сразу следует общая закономерность
![$$a \equiv b \mod N_p^k \ \ \Rightarrow \ \ F_a^k \equiv F_b^k \mod p,$$ $$a \equiv b \mod N_p^k \ \ \Rightarrow \ \ F_a^k \equiv F_b^k \mod p,$$](https://dxdy-01.korotkov.co.uk/f/c/4/f/c4fe365d49457b838b77a6403ba85a5782.png)
а также несколько утверждений для составных модулей, которые строго доказать не берусь:
Исправлено 19.09.2019Порядок расположения нулей внутри периода последовательности
![$F_n^k \mod p$ $F_n^k \mod p$](https://dxdy-01.korotkov.co.uk/f/c/c/f/ccf71899541c70e6e255309f5bb56f3382.png)
– вопрос отдельный. В случае
![$k=1$ $k=1$](https://dxdy-04.korotkov.co.uk/f/7/e/b/7eb22be4bf74527b54b6d6093847814782.png)
их нет вообще, а значение
![$N^1_{p>2}$ $N^1_{p>2}$](https://dxdy-04.korotkov.co.uk/f/3/e/5/3e5cab5b7fbbf3469801e535651545b982.png)
совпадает со значением дискретного логарифма по основанию
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
. В случае
![$k=2$ $k=2$](https://dxdy-03.korotkov.co.uk/f/e/0/2/e021cb770c745ec45faa5ae82936a9b882.png)
расположение нулей внутри периода также периодично. "Малый" период может быть равен
![$N_p^2,N_p^2/2$ $N_p^2,N_p^2/2$](https://dxdy-03.korotkov.co.uk/f/6/7/b/67bf5e130149b329b98e1ad51d6840b382.png)
или
![$N_p^2/4$ $N_p^2/4$](https://dxdy-04.korotkov.co.uk/f/b/0/0/b00dcab0594ac6be040ae1150e4d3a2482.png)
. Об этом можно почитать, пройдя по
ссылке maxal, там же описан метод вычисления малого периода непрерывными дробями. Но вот в случае
![$k>2$ $k>2$](https://dxdy-03.korotkov.co.uk/f/a/5/f/a5f6f1052ef59b00868159d9d1a605c982.png)
нули непериодичны; об этом чуть позже, пока приведу пример
![$$F_n^3 \mod 3=(1,1,1,2,0,1,0,0)$$ $$F_n^3 \mod 3=(1,1,1,2,0,1,0,0)$$](https://dxdy-02.korotkov.co.uk/f/9/3/d/93d30f2f190c7db13a1bafaf9236820182.png)
Как видим, решение уравнения
![$F^2_x \ \vdots \ 3$ $F^2_x \ \vdots \ 3$](https://dxdy-02.korotkov.co.uk/f/d/c/f/dcf5a710c1f4161f44effe8111de04fc82.png)
записывается короче, чем
![$F^3_x \ \vdots \ 3$ $F^3_x \ \vdots \ 3$](https://dxdy-02.korotkov.co.uk/f/1/5/0/15089da7759546c8295c861f555e99b282.png)
. В первом случае
![$x \equiv 0 \mod 4$ $x \equiv 0 \mod 4$](https://dxdy-04.korotkov.co.uk/f/7/2/9/7295c9fca4768264d76f4b23fed7121882.png)
, во втором
![$x \equiv 5,7,0 \mod 8$ $x \equiv 5,7,0 \mod 8$](https://dxdy-01.korotkov.co.uk/f/8/4/5/84532ba27f44c59e3fd05f249b8b003e82.png)
. Тут, однако, возникают вопросы.
1) Обязательно ли период включает в себя
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
начальных единиц? Это было бы удобно, т.к. других методов вычисления
![$N^k_p$ $N^k_p$](https://dxdy-02.korotkov.co.uk/f/5/8/f/58fa86774918e2e7afaab9c203da85a582.png)
кроме перебора по
![$\mod p$ $\mod p$](https://dxdy-03.korotkov.co.uk/f/6/6/e/66e148472efdce1b3f5d503182c84fb582.png)
не известно, но что если период начинается с
![$k+1$ $k+1$](https://dxdy-04.korotkov.co.uk/f/3/3/3/33359de825e43daa97171e27f6558ae982.png)
-го знака?
2) Почему, собственно, нули вообще должны содержаться в периоде? Что если члены одной из рассматриваемых последовательностей не делятся к примеру на
![$127$ $127$](https://dxdy-02.korotkov.co.uk/f/1/b/0/1b0252422be59dcb30ab66845291d7cd82.png)
? Справедливо же это для
![$F^1_n$ $F^1_n$](https://dxdy-01.korotkov.co.uk/f/4/6/a/46a7cb93412808663bdd9336109d2a4782.png)
.
Перепишем рекуррентное правило
![$F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$ $F_n^{k}=F_{n-1}^{k}+F_{n-k}^{k}$](https://dxdy-02.korotkov.co.uk/f/1/a/4/1a4b2f04da1f28e3a9da9ed746e60baf82.png)
так:
![$F_{n-k}^{k}=F_n^{k}-F_{n-1}^{k}.$ $F_{n-k}^{k}=F_n^{k}-F_{n-1}^{k}.$](https://dxdy-04.korotkov.co.uk/f/b/a/2/ba29bdefe9e0f10fef7845bad97b3cf282.png)
Здесь до сих пор рассматривались последовательности положительных чисел,
но в случае ![$k>1$ $k>1$](https://dxdy-01.korotkov.co.uk/f/8/7/3/8733ac5ecc35ea70e3e236ade3c28a6082.png)
ничто не мешает продолжить их влево
![$(n<1)$ $(n<1)$](https://dxdy-02.korotkov.co.uk/f/d/7/a/d7ae79d6cc752aeccdb2d3c8e34a926282.png)
, и всё сказанное выше о делимости
![$F^k_n$ $F^k_n$](https://dxdy-04.korotkov.co.uk/f/b/3/8/b38c2621c45447862886739fac57e8ba82.png)
остается в силе. В частности, предыдущий пример можно было получить из двух/трех последовательных единиц в обратном порядке. Иными словами, каждые
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
последовательных члена полностью определяют последовательность остатков не только в прямом, но и в обратном движении, любой номер можно взять "точкой отсчета", и предположение о существовании членов, не входящих в период приводит тогда к противоречию. Далее видим, что для всех последовательностей,
за исключением ![$k=1$ $k=1$](https://dxdy-04.korotkov.co.uk/f/7/e/b/7eb22be4bf74527b54b6d6093847814782.png)
определено
![$F^k_0=F^k_k-F^k_{k-1}=1-1=0.$ $F^k_0=F^k_k-F^k_{k-1}=1-1=0.$](https://dxdy-02.korotkov.co.uk/f/9/1/5/915d7745f65ed5ab0bd5e7ba41d3367c82.png)
Оно делится на любое
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, и, значит, через
![$N^k_p$ $N^k_p$](https://dxdy-02.korotkov.co.uk/f/5/8/f/58fa86774918e2e7afaab9c203da85a582.png)
номеров получим еще хотя бы один член кратный
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
, например
![$p=127$ $p=127$](https://dxdy-04.korotkov.co.uk/f/7/f/6/7f6c2a706f2d53b19479a9f947be4b9482.png)
. Продолжая строить последовательность влево от единиц по
![$\mod p$ $\mod p$](https://dxdy-03.korotkov.co.uk/f/6/6/e/66e148472efdce1b3f5d503182c84fb582.png)
, получаем в обратном порядке
![$k-1$ $k-1$](https://dxdy-03.korotkov.co.uk/f/a/a/9/aa9d1dc08f682f546eeee2869762ff9082.png)
нулей, единицу,
![$k-2$ $k-2$](https://dxdy-02.korotkov.co.uk/f/9/0/8/9083e7d39713ae371c52b3bbdc7eac0e82.png)
нуля,
![$p-1$ $p-1$](https://dxdy-02.korotkov.co.uk/f/5/8/5/585cf0d6605a58bb5df9e272ae37244a82.png)
. Это доказывает невозможность периодического расположения нулей внутри периода для
![$k>2$ $k>2$](https://dxdy-03.korotkov.co.uk/f/a/5/f/a5f6f1052ef59b00868159d9d1a605c982.png)
. Наиболее близки к этому состоянию
![$N^p_p=p^2-1$ $N^p_p=p^2-1$](https://dxdy-03.korotkov.co.uk/f/6/8/c/68c02b4f7e6f666dc090411102a439a682.png)
и более общий случай
![$N^{(p^r)}_p=p^{2r}-1$ $N^{(p^r)}_p=p^{2r}-1$](https://dxdy-04.korotkov.co.uk/f/3/6/a/36af34bad3dc134dada9383338ac228f82.png)
(относительно короткие периоды). Таблица некоторых значений
![$N^k_p<50000$ $N^k_p<50000$](https://dxdy-03.korotkov.co.uk/f/6/8/7/687bcafb5ff48e545dfb60e83fc1968482.png)
выглядит так:
![$$\begin{matrix}
& p & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19\\
k & + & --- & --- & --- & --- & --- & --- & --- & ---\\
1 & | & 1 & 2 & 4 & 3 & 10 & 12 & 8 & 18\\
2 & | & 3 & 8 & 20 & 16 & 10 & 28 & 36 & 18\\
3 & | & 7 & 8 & 31 & 57 & 60 & 168 & 288 & 381\\
4 & | & 15 & 80 & 312 & 342 & 1330 & 2196 & 96 & 14480\\
5 & | & 21 & 78 & 24 & 336 & 120 & 366 & 288 & 180\\
6 & | & 63 & 728 & 3124 & 2400 & & & & \\
7 & | & 127 & 728 & 19531 & 48 & & & & \\
8 & | & 63 & 3146 & 2232 & & & & &
\end{matrix}$$ $$\begin{matrix}
& p & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19\\
k & + & --- & --- & --- & --- & --- & --- & --- & ---\\
1 & | & 1 & 2 & 4 & 3 & 10 & 12 & 8 & 18\\
2 & | & 3 & 8 & 20 & 16 & 10 & 28 & 36 & 18\\
3 & | & 7 & 8 & 31 & 57 & 60 & 168 & 288 & 381\\
4 & | & 15 & 80 & 312 & 342 & 1330 & 2196 & 96 & 14480\\
5 & | & 21 & 78 & 24 & 336 & 120 & 366 & 288 & 180\\
6 & | & 63 & 728 & 3124 & 2400 & & & & \\
7 & | & 127 & 728 & 19531 & 48 & & & & \\
8 & | & 63 & 3146 & 2232 & & & & &
\end{matrix}$$](https://dxdy-02.korotkov.co.uk/f/5/f/9/5f9338073965b85ca957fa7502eb2ca182.png)