Тест простоты для чисел вида 4 \cdot 345 \cdot 139^n-269

[Pedja]

Следующая гипотеза является частным случаем предполагаемых тестов типа Люка-Лемера для чисел вида $4kp^n \pm c$ где $$$ p $— простое число, а $c $— нечётное целое число.

Гипотеза

Пусть число $M_n$ для $n \ge 1$ определяется как $M_n = 4 \cdot 345 \cdot 139^n - 269$ и пусть индекс $ m$ определяется как $m = 345 \cdot 139^n - 67$ . Пусть $T_p(x)$ — полином Чебышёва первого рода p-го порядка. Тогда $M_n$ является простым числом тогда и только тогда, когда $T_m(T_{345}(2)) \equiv 0 \pmod{M_n}$ .

Вы можете запустить этот тест здесь. Здесь вы можете найти доказательство необходимости.

Может ли кто-нибудь предоставить доказательство достаточности или контрпример?

[maxal]

А какой смысл записывать явно композицию полиномов Чебышева, если мы знаем, что $T_m(T_{345}(x))=T_{345m}(x)$ ?

[Pedja]

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

А какой смысл записывать явно композицию полиномов Чебышева, если мы знаем, что $T_m(T_{345}(x))=T_{345m}(x)$ ?

Вы, конечно, правы. Это не имеет смысла.

[maxal]

Так как $T_k(2)=V_k(4,1)/2$ - ополовиненная последовательность Люка с дискриминантом $12$, $M_n = 4m-1$ и символ Якоби $\left(\frac{12}{M_n}\right) = \left(\frac{3}{M_n}\right) = -\left(\frac{M_n}3\right)=-1$, то $M_n$ будет псеводопростым Люка, если $U_{4m} = U_{m}V_mV_{2m} \equiv 0\pmod{M_n}$. Вы по сути доказали, что для простого $M_n$, $T_m(2)\equiv V_m(4,1)\equiv 0\pmod{M_n}$, что влечет как условие теста Люка, так и $T_{345m}(2)\equiv 0\pmod{M_n}$. Однако непонятно, чем предложенный тест лучше теста Люка, у которого кроме того есть "сильные" варианты, а также чем обусловлен множитель $345$ перед $m$ (с тем же успехом можно взять любое другое нечётное число).

Известно, что тест Люка допускает наличие псевдопростых, однако среди таких разряженных (ввиду экспоненциального роста) чисел как $M_n$ их может не существовать, как, впрочем, и у предложенного теста.