Investigation if a given number is prime. (Q1548961): Difference between revisions

Um zu untersuchen, ob eine gegebene ungrade Zahl eine Primzahl ist oder nicht, sucht der Verfasser dieselbe auf die Form \(n=x^2-y^2\) zu bringen. Ist \(n\) eine Primzahl, so ist dieses nur auf eine Weise möglich, sonst giebt es mehrere Darstellungen, indem \[ n_{1}n_{2}=\left({n_{1}+n_{2}\over {2}}\right)^2-\left({n_{1}-n_{2}\over {2}}\right)^2. \] Ist also \(n\) eine teilbare Zahl, so liegt \(x\) zwischen \({1 \over {2}}(n+1)\) und \(\sqrt{n}\). Diese Grenzen werden bedeutend verengert, indem man teils direct die Teilbarkeit mit den ersten Primzahlen untersucht, teils versucht, ob vielleicht kleine Werte von \(y\) die Gleichung befriedigen. Eine fernere Reduction der Grenzen kann man erhalten, wenn man \(n\) mit einer bekannten Zahl \(f=a^{2}-b^{2}\) multiplicirt, und dann \[ fn=(x^{2}-y^{2})(a^{2}-b^{2})=(ax-by)^{2}-(bx-ay)^{2}=X^{2}-Y^{2} \] untersucht, und namentlich die Probe macht mit kleinen Werten von \(Y\). Eine genaue Betrachtung der Endziffer von \(n\) macht eine rein mechanische Ausscheidung so vieler Werte von \(x\) möglich, dass nur noch bei wenigen eine directe Probe nötig ist. Die Methode wird an der Primzahl 9738017 erläutert.