Quadratic residues in factorization. (Q2622780)

Mit Hilfe des \textit{Jacobis}chen Symbols werden in bekannter Weise Quasireste (apparent residues) und Quasinichtreste einer Zahl \(N\) definiert. Es gilt der Satz: Sind alle Quasireste einer Zahl \(N\) wirkliche quadratische Reste, so ist \(N\) entweder eine Primzahl oder die Potenz einer Primzahl. Nützlicher für die Untersuchung, ob eine große Zahl Primzahl ist, ist die folgende Formulierung. Sei \(L_p\) die kleinste Zahl, welche für alle Primzahlen \( \leqq p\) quadratischer Rest ist, ohne eine Quadratzahl zu sein. Man bestimme \(p\) so, daß alle echten Teiler von \(N\) unterhalb \(L_p\) liegen. Man betrachte die Zahlen \(-1,2,-3,\ldots,\left (\frac {-1}{p}\right )p\) und bestimme unter ihnen die Quasireste \(a_1,a_2,\ldots \) und die Quasinichtreste \(b_1,b_2,\ldots \) von \(N\). Sind alle \(a_i\) und alle Produkte \(b_ib_j\) wirkliche quadratische Reste von \(N\), so ist \(N\) Primzahl oder Primzahlpotenz.