Lucas polinomlarının faktörlerini kullanarak belirli doğal sayılar sınıfı için asallık testi

Question

Bu soru bir önceki sorumla ilgili .

Aşağıdaki iddiayı kanıtlayabilir veya çürütebilir misiniz:

İzin Vermek $N=2n+1$ nerede $n$ birden büyük tek bir doğal sayıdır, let $L_m(x)$ mth Lucas polinomu olun ve $F_m(x)$ indirgenemez bir derece faktörünü gösterir $\varphi(m)$ nın-nin $L_m(x)$. Bir tam sayı varsa$a$ öyle ki $F_{n}(a) \equiv 0 \pmod{N} $ sonra $N$ bir asaldır.

Bu testi burada çalıştırabilirsiniz . Bu iddiayı yalnızca küçük değerler için doğruladım$N$ , yani $N \in [7,1000]$ ile $a \in [1,100]$ , çünkü testin PARI / GP uygulamam çok yavaş.

DÜZENLE

Değerleri için $n$tek asal sayılar olan bu test, polinom zamanda çalıştırılır ( PARI / GP uygulaması ). Sophie Germain asallarının listesi burada bulunabilir .

Answer 1

Bu hak, esas olarak aynı şekilde de ispat edilebilir bir önceki . Sahibiz$$F_n(x)=\prod_{\substack{|m|<n/2\\(m,n)=1}}(x+\zeta^m-\zeta^{-m}),$$ nerede $\zeta\in\mathbb{C}$ ilkel $2n$-birliğin. kökü. Bölme alanı$F_n(x)$ ... $n$- siklotomik alan.

Varsayalım ki $q\nmid n$ bir asal sayıdır, öyle ki azalması $F_n(x)$ mod $q$ kök salmış $\mathbb{F}_q$. Kökleri$F_n(x)$ içinde $\overline{\mathbb{F}_q}$ formda $\xi^m-\xi^{-m}$, nerede $\xi\in\overline{\mathbb{F}_q}$ ilkel $2n$-birliğin. kökü. Varsayım olarak, Frobenius otomorfizmi$t\mapsto t^q$ bu köklerden birini düzeltir, bu yalnızca $q\equiv 1\pmod{2n}$. Bunu takip eder, herhangi biri için$a\in\mathbb{Z}$ana faktörleri $F_n(a)$ coprime to $n$ uyumlu $1$ modulo $2n$. Özellikle, eğer$2n+1$ böler $F_n(a)$, o zaman tek asal faktör $2n+1$ kendisi olabilir, yani $2n+1$ asal.