Kiểm tra tính nguyên tố cho lớp số tự nhiên cụ thể bằng cách sử dụng nhân tử của đa thức Lucas

Question

Câu hỏi này có liên quan đến câu hỏi trước đây của tôi .

Bạn có thể chứng minh hoặc bác bỏ tuyên bố sau:

Để cho $N=2n+1$ Ở đâu $n$ là một số tự nhiên lẻ lớn hơn một, hãy $L_m(x)$ là đa thức Lucas thứ m và để $F_m(x)$ biểu thị một hệ số bất khả quy về mức độ $\varphi(m)$ của $L_m(x)$. Nếu tồn tại một số nguyên$a$ như vậy mà $F_{n}(a) \equiv 0 \pmod{N} $ sau đó $N$ là một số nguyên tố.

Bạn có thể chạy thử nghiệm này tại đây . Tôi đã xác minh tuyên bố này chỉ cho các giá trị nhỏ của$N$ , đó là $N \in [7,1000]$ với $a \in [1,100]$ , bởi vì việc triển khai PARI / GP của tôi trong thử nghiệm quá chậm.

BIÊN TẬP

Đối với các giá trị của $n$đó là các số nguyên tố lẻ, thử nghiệm này chạy trong thời gian đa thức ( triển khai PARI / GP ). Danh sách các số nguyên tố Sophie Germain có thể được tìm thấy tại đây .

Answer 1

Tuyên bố này có thể được chứng minh về cơ bản giống như cách trước đó . Chúng ta có$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ Ở đâu $\zeta\in\mathbb{C}$ là một người nguyên thủy $2n$- gốc rễ của sự thống nhất. Trường tách của$F_n(x)$ là $n$-th trường cyclotomic.

Giả sử $q\nmid n$ là một số nguyên tố sao cho giảm $F_n(x)$ mod $q$ có gốc rễ trong $\mathbb{F}_q$. Rễ của$F_n(x)$ trong $\overline{\mathbb{F}_q}$ có dạng $\xi^m-\xi^{-m}$, Ở đâu $\xi\in\overline{\mathbb{F}_q}$ là một người nguyên thủy $2n$- gốc rễ của sự thống nhất. Theo giả định, tính tự động Frobenius$t\mapsto t^q$ sửa một trong những gốc này, chỉ có thể thực hiện được khi $q\equiv 1\pmod{2n}$. Nó theo sau đó, cho bất kỳ$a\in\mathbb{Z}$, các yếu tố chính của $F_n(a)$ coprime $n$ đồng ý với $1$ modulo $2n$. Đặc biệt, nếu$2n+1$ phân chia $F_n(a)$, thì thừa số nguyên tố duy nhất của $2n+1$ có thể là chính nó, tức là, $2n+1$ là nguyên tố.