Conditional Lucas Pseudoprimes

Abstract

Define the conditional recurrence sequence \(q_n = aq_{n-1} + bq_{n-2}\) if \(n\) is even, \(q_n = bq_{n-1} + cq_{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{\Delta}{n})}\), where \(\Delta = a^2 + b^2 + 4ab\) and \((\frac{\Delta}{n})\) denotes the Jacobi symbol. We prove that if \((n, 2ab\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?