Some primality tests that eluded Lucas (Q887438): Difference between revisions

In the XIX century É. Lucas provided deterministic primality tests for numbers \(N\),\, where \(N\pm 1\)\, is divisible by a large power of a (small) prime \(r\), tests based on properties of the so-called Lucas sequences \(\{u_n\},\{v_n\}\)\, (linear recurring sequences of order two), see [\textit{H. C. Williams}, Édouard Lucas and primality testing. New York, NY: John Wiley \& Sons (1998; Zbl 1155.11363)]. But ``no proof were provided for these tests, and they are not correct as stated''. The aim of the present paper is first ``to correct and generalize Lucas's primality tests'' and second ``to provide further support of Lucas's view that an investigation of (linear) recurring sequences of order 4 would yield new properties of prime numbers''. Section 2 deals with the first objective, generalizing and giving correct proofs of primality tests for the Lucas's numbers \(N=Ar^n+\gamma\), \(\gamma^2=1 \) (Theorems 2.8, 2.9 and 2.10). The rest of sections are devoted to the second objective. Section 3 studies properties of the order 4 recurring sequences \(\{U_n\},\{V_n\}\), see [\textit{H. C. Williams} and \textit{R. K. Guy}, Int. J. Number Theory 7, No. 5, 1255--1277 (2011; Zbl 1237.11006)], Section 4 studies the computational complexity for computing these numbers modulo \(N\)\, and Sections 5 and 6 properties of a sequence \(\{G_n\}\)\, derived from \(\{U_n\},\{V_n\}\). Primality tests similar to Lucas's test for numbers \(N=Ar^n+ \eta\gamma_n(r)\)\, where \(\eta^2=1\)\, and \(\gamma_n(r)\)\, a solution of \(x^2\equiv -1 \bmod r^n\),\, are given in Section 7 (Theorems 7.2 and 7.4). The particular case \(r=5\)\, is treated in Theorem 7.5. The authors point out that for \(r=5\)\, another primality test is giving by \textit{P. Berrizbeitia} et al. [Theor. Comput. Sci. 297, No. 1--3, 25--36 (2003; Zbl 1048.11101)] but ``the proof techniques are much different from ours''.