Тест на простоту для определенного класса натуральных чисел с использованием множителей многочленов Люка
Этот вопрос связан с моим предыдущим вопросом .
Можете ли вы доказать или опровергнуть следующее утверждение:
Позволять $N=2n+1$ где $n$ нечетное натуральное число больше единицы, пусть $L_m(x)$ - m-й многочлен Люка, и пусть $F_m(x)$ обозначают неприводимый множитель степени $\varphi(m)$ из $L_m(x)$. Если существует целое число$a$ такой, что $F_{n}(a) \equiv 0 \pmod{N} $ тогда $N$ это простое число.
Вы можете запустить этот тест здесь . Я проверил это утверждение только для небольших значений$N$ , это $N \in [7,1000]$ с участием $a \in [1,100]$ , потому что моя реализация теста PARI / GP слишком медленная.
РЕДАКТИРОВАТЬ
Для значений $n$которые являются нечетными простыми числами, этот тест выполняется за полиномиальное время (реализация PARI / GP ). Список простых чисел Софи Жермен можно найти здесь .
Ответы
Это утверждение может быть доказано практически так же, как и предыдущее . У нас есть$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ где $\zeta\in\mathbb{C}$ примитивный $2n$-й корень из единства. Поле расщепления$F_n(x)$ это $n$-й круговое поле.
Предположим, что $q\nmid n$ - такое простое число, что уменьшение $F_n(x)$ мод $q$ имеет корень в $\mathbb{F}_q$. Корни$F_n(x)$ в $\overline{\mathbb{F}_q}$ имеют форму $\xi^m-\xi^{-m}$, где $\xi\in\overline{\mathbb{F}_q}$ примитивный $2n$-й корень из единства. По предположению автоморфизм Фробениуса$t\mapsto t^q$ исправляет один из этих корней, что возможно только при $q\equiv 1\pmod{2n}$. Отсюда следует, что для любого$a\in\mathbb{Z}$, простые множители $F_n(a)$ взаимно простой с $n$ конгруэнтны $1$ по модулю $2n$. В частности, если$2n+1$ разделяет $F_n(a)$, то единственный простой делитель $2n+1$ может быть самим собой, т.е. $2n+1$ простое.