Lots and lots of Perrin-type primality tests and their pseudo-primes (Q6546694)

The paper provides a method to construct ``lots and lots'' of primality tests of Perrin-type. For some of them it is possible to give explicitly infinite families of pseudoprimes.\N\NThe Perrin probabilistic primality text, see [\textit{R. Perrin}, Item 1484, L' Intermédière des Math. 6, 76--77 (1889)], it is based in a recurrence sequence \(\{A_n\}_{n\ge 1}\)\, with the property that for all \(p\) prime, \(p\mid A_p\). This condition is not sufficient for the primality of \(p\) since there are infinite Perrin pseudoprimes.\N\N\textit{V. Vatter} gives a combinatorial proof of the property \(p\mid A_p\),\, see [Math. Horizons 29, No. 1 (2022)]. That proof suggests the present method. \par\N\NThe method is described in Section 2. The paper considers relations \(P(x)/Q(x)=\sum a_nx^n\), where \(Q(x)=1-e_1x+e_2x^2+\dots +(-1)^ke_kx^k\)\, can be any polynomial with integer coefficients and \(Q(0)=1\), \(P(x)\)\, is an integer polynomial depending only of \(Q(x)\)\, and such that the \(a_i\in \mathbb{Z}\).\N\NThe primality test is given by the property \(a_p\equiv e_1 \bmod p\), for \(p\)\, prime. This test is implemented in the symbolic computation packing MAPLE.\N\NSection 3 shows examples of those tests for which explicit and infinite families of pseudoprimes can be given (Theorems 1 to 5).