Uji primalitas untuk kelas tertentu bilangan asli menggunakan faktor polinomial Lucas

Question

Pertanyaan ini terkait dengan pertanyaan saya sebelumnya .

Dapatkah Anda membuktikan atau menyangkal klaim berikut:

Membiarkan $N=2n+1$ dimana $n$ adalah bilangan asli ganjil yang lebih besar dari satu, misalkan $L_m(x)$ jadilah polinomial Lucas bln dan biarkan $F_m(x)$ menunjukkan faktor derajat yang tidak dapat direduksi $\varphi(m)$ dari $L_m(x)$. Jika ada bilangan bulat$a$ seperti yang $F_{n}(a) \equiv 0 \pmod{N} $ kemudian $N$ adalah bilangan prima.

Anda dapat menjalankan tes ini di sini . Saya telah memverifikasi klaim ini hanya untuk nilai kecil$N$ , itu adalah $N \in [7,1000]$ dengan $a \in [1,100]$ , karena pelaksanaan tes PARI / GP saya terlalu lambat.

EDIT

Untuk nilai $n$yang merupakan bilangan prima ganjil pengujian ini berjalan dalam waktu polinomial ( implementasi PARI / GP ). Daftar bilangan prima Sophie Germain dapat ditemukan di sini .

Answer 1

Klaim ini pada dasarnya dapat dibuktikan dengan cara yang sama seperti yang sebelumnya . Kita punya$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ dimana $\zeta\in\mathbb{C}$ adalah primitif $2n$akar -th dari persatuan. Bidang pemisahan$F_n(x)$ adalah $n$-tempat siklotomik.

Asumsikan bahwa $q\nmid n$ adalah bilangan prima sehingga pengurangan $F_n(x)$ mod $q$ berakar $\mathbb{F}_q$. Akar dari$F_n(x)$ di $\overline{\mathbb{F}_q}$ adalah dari bentuknya $\xi^m-\xi^{-m}$, dimana $\xi\in\overline{\mathbb{F}_q}$ adalah primitif $2n$akar -th dari persatuan. Dengan asumsi, automorfisme Frobenius$t\mapsto t^q$ memperbaiki salah satu akar ini, yang hanya mungkin jika $q\equiv 1\pmod{2n}$. Oleh karena itu, untuk semua$a\in\mathbb{Z}$, faktor prima dari $F_n(a)$ coprime untuk $n$ kongruen dengan $1$ modulo $2n$. Secara khusus, jika$2n+1$ membagi $F_n(a)$, maka satu-satunya faktor prima dari $2n+1$ bisa menjadi dirinya sendiri, yaitu, $2n+1$ adalah bilangan prima.