Test pierwszości dla określonej klasy liczb naturalnych z wykorzystaniem współczynników wielomianów Lucasa
To pytanie jest związane z moim poprzednim pytaniem .
Czy możesz udowodnić lub odrzucić następujące roszczenie:
Pozwolić $N=2n+1$ gdzie $n$ jest nieparzystą liczbą naturalną większą niż jeden, niech $L_m(x)$ być m-tym wielomianem Lucasa i niech $F_m(x)$ oznaczają nieredukowalny współczynnik stopnia $\varphi(m)$ z $L_m(x)$. Jeśli istnieje liczba całkowita$a$ takie że $F_{n}(a) \equiv 0 \pmod{N} $ następnie $N$ jest liczbą pierwszą.
Możesz uruchomić ten test tutaj . Sprawdziłem to twierdzenie tylko dla małych wartości$N$ , to jest $N \in [7,1000]$ z $a \in [1,100]$ , ponieważ moja implementacja testu PARI / GP jest zbyt wolna.
EDYTOWAĆ
Dla wartości $n$które są nieparzystymi liczbami pierwszymi, ten test działa w czasie wielomianowym ( implementacja PARI / GP ). Listę liczb pierwszych Sophie Germain można znaleźć tutaj .
Odpowiedzi
Twierdzenie to można udowodnić zasadniczo w taki sam sposób, jak poprzednie . Mamy$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ gdzie $\zeta\in\mathbb{C}$ jest prymitywem $2n$-ty rdzeń jedności. Pole podziału$F_n(x)$ jest $n$-te pole cyklotomiczne.
Zakładać, że $q\nmid n$ jest liczbą pierwszą taką, że redukcja $F_n(x)$ mod $q$ ma korzenie $\mathbb{F}_q$. Korzenie$F_n(x)$ w $\overline{\mathbb{F}_q}$ mają formę $\xi^m-\xi^{-m}$, gdzie $\xi\in\overline{\mathbb{F}_q}$ jest prymitywem $2n$-ty rdzeń jedności. Z założenia automorfizm Frobeniusa$t\mapsto t^q$ naprawia jeden z tych korzeni, co jest możliwe tylko wtedy, gdy $q\equiv 1\pmod{2n}$. Wynika z tego, że dla każdego$a\in\mathbb{Z}$, główne czynniki $F_n(a)$ względnie pierwsze do $n$ są przystające do $1$ modulo $2n$. W szczególności, jeśli$2n+1$ dzieli $F_n(a)$, to jedyny główny czynnik $2n+1$ może być sobą, tj. $2n+1$ jest liczbą pierwszą.