"странная" задача о периодах и числах Софи Жермен

[maxal]

Пусть $(p,2p+1)$ - простые числа Софи Жермен.

Докажите, что всякого целого числа $c$ можно найти целое число $c'$ такое, что периоды линейных рекуррентных последовательностей

$$a_0 = 0,\quad a_1=1,\quad a_{k+1} = (c\cdot a_k - a_{k-1}) \bmod p,\ k\geq 1$$

и

$$b_0 = 0,\quad b_1=1,\quad b_{k+1} = (c'\cdot b_k - b_{k-1}) \bmod (2p+1),\ k\geq 1$$

равны.

(источник)

[Руст]

Приходится рассмотреть много случаев отдельно. Рассмотрим для произвольного простого числа р все возможные реализации периода. Отдельно рассмотрим малые простые значения.
р=2, с=0. Последовательность $a_n=n\mod 2$ - период 2.
р=2, с=1. Последовательность $a_n=0,1,1,0,1,1,...$ - период 3.

р=3, с=0. Последовательность $a_n=0,1,0,2,0,1,...$ - период 4.
р=3, с=1. Последовательность $a_n=0,1,1,0,2,2,0,1,...$ - период 6.
р=3,с=2. Последовательность $a_n=n\mod p$ - период 3.

р=5, с=0. Последовательнотсь $a_n=0,1,0,4,0,1,...$ - период 4.
р=5,с=1. Последовательность $a_n=0,1,1,0,4,4,0,1,...$ - период 6.
p=5,c=2. Последовательность $a_n=n\mod p$ - период р=5.
р=5,с=3=-2. Последовательность $a_n=(-1)^{n-1}n$ - период 2р=10.
р=5,с=4. Последовательность $a_n=0,1,4,0,1,...$ - период 3.
Как видно, уже при p=2,c=0 не выполняется условие задачи.

Общий случай $p>5$. Характеристическое уравнение $x^2-cx+1=0$. Решение $x=a=\frac{c+\sqrt{c^2-4}}{2},\frac 1a.$
с=2. Решение $a_n=n\mod p$ - период р.
с=-2=р-2. Решение $a_n=(-1)^{n-1}n$ - период 2р.
$c^2-4$ - квадратичный вычет по модулю р. Тогда корни из $Z/pZ$ ($a,a^{-1}$) реализуются все случаи ($c=a+\frac 1a $). Соответственно решение

$$a_n=\frac{a^n-a^{-n}}{a-a^{-1}}, a\not =\pm 1.$$

Период $ord_p(a)$. Когда $n=ord_p(a)/2$, число $a_n=0$, однако $a_{n+1}=-1\not =1$. Реализуются все делители $p-1$ большие 2.
$c^2-4$ - квадратичный невычет. В этом случае корни из квадратичного расширения $Z/pZ$. При этом $a^p=\frac 1a$. Т.е. период является делителем числа $p+1}$. Здесь так же реализуется все делители большее 2.
Таким образом утверждение неверное.
Например $p=11,c=3$ - период 5 и не равен периоду по модулю 23 ни при каком $c'$.

[Sonic86]

Руст в сообщении #470368 писал(а):

$c^2-4$ - квадратичный невычет. В этом случае корни из квадратичного расширения $Z/pZ$. При этом $a^p=\frac 1a$. Т.е. период является делителем числа $p+1$.

Можно спросить - почему это верно Не знаю, в какой книжке посмотреть (в Лидле Нидеррайтере не нашел). Если мы берем квадратичное расширение $\mathbb{Z}_p[\sqrt{d}]$, то оно $\cong \mathbb{F}_{p^2}$, у него $\mathbb{F}_{p^2}^{\times}$ циклична и значит есть элементы любого порядка, делящего $p^2-1$. Кроме того, если взять числа Фибоначчи, то у них по модулю $p=7$ период равен $16$ - не делит $p+1$. Хотя для положительных дискриминантов у меня период всего выходит делителем $p+1$. Значит еще от знака дискриминанта период зависит. Почему?

(Оффтоп)

извините за глупые вопросы

[Руст]

Sonic86 в сообщении #470467 писал(а):

Руст в сообщении #470368 писал(а):

$c^2-4$ - квадратичный невычет. В этом случае корни из квадратичного расширения $Z/pZ$. При этом $a^p=\frac 1a$. Т.е. период является делителем числа $p+1$.

Можно спросить - почему это верно Не знаю, в какой книжке посмотреть (в Лидле Нидеррайтере не нашел). Если мы берем квадратичное расширение $\mathbb{Z}_p[\sqrt{d}]$, то оно $\cong \mathbb{F}_{p^2}$, у него $\mathbb{F}_{p^2}^{\times}$ циклична и значит есть элементы любого порядка, делящего $p^2-1$. Кроме того, если взять числа Фибоначчи, то у них по модулю $p=7$ период равен $16$ - не делит $p+1$. Хотя для положительных дискриминантов у меня период всего выходит делителем $p+1$. Значит еще от знака дискриминанта период зависит. Почему?

(Оффтоп)

извините за глупые вопросы

Дело в том, что здесь корни удовлетворяют уравнению $a^{p+1}=1$. В общем случае $x+y\sqrt d$, где $d$ квадратичный невычет получается $(x+y\sqrt d)^{p+1}=(x+y\sqrt d)(x^p+y^pd^{(p-1)/2}\sqrt d)=(x+y\sqrt d)(x-y\sqrt d)=x^2-dy^2$.
Если $x+y\sqrt d$ корень квадратного уравнения $z^2-cz+b=0,$ то [math]$$x=c/2, y=1,d=(c^2-4b)/4, x^2-dy^2=b.$$
В нашем случае b=1.
Поэтому период делитель $p+1.$
В случае Фибоначи $b=-1.$ и период делитель $2(p+1)$ для случая квадратичного невычета.
В общем случае можно говорит только о делителе $p^2-1$.

[Sonic86]

О! Понял! Спасибо!

[Руст]

На самом деле если в условии $\forall c$ добавить: "такого, что $(\frac{c^2-4}{p})=-1$", то задача становится корректной.
Доказывается показом того, что для любого $d>2, d|p+1$ найдется такое с, что последовательность $a_n$ будет иметь период d. Достаточно взять мультипликативную образующую $x+y\sqrt g$ квадратичного расширения и возвести в степень $\frac{p^2-1}{d}$. Тогда полученное число имеет норму 1 и представляется в виде квадратичной иррациональности $z+\sqrt{z^2-1}$ (случай d=1- соответствует z=1, d=2 случаю z=-1) с нормой $x^2-gy^2$ равной 1. Тогда можно взять c=2z.