Conditional Lucas Pseudoprimes

Abstract

Define the conditional recurrence sequence $q_n=a{q}_{n-1}+b{q}_{n-2}$ if $n$ is even, $q_n=b{q}_{n-1}+c{q}_{n-2}$ if $n$ is odd, where $q_0=0,q_1=1$. Then $q_n$ satisfies a fourth-order recurrence while both $q_{2n}$ and $q_{2n+1}$ satisfy a second-order recurrence.

Analogously to a Lucas pseudoprime, we define a composite number $n$ to be a conditional Lucas pseudoprime (clpsp) if $n$ divides $q_{n–(\frac{\mathrm{\Delta }}{n})}$, where $\mathrm{\Delta }=a^2+b^2+4ab$ and $(\frac{\mathrm{\Delta }}{n})$ denotes the Jacobi symbol. We prove that if $(n,2ab\mathrm{\Delta })=1$, then there are infinitely many conditional Lucas pseudoprimes. We also address the question, given an odd composite integer $n$, for how many pairs $(a,b)$ is $n$ a conditional Lucas pseudoprime?