A Frobenius Trichotomy for Rotkiewicz's Semiprime Fibonacci Pseudoprime Families

Abstract

Rotkiewicz characterized three semiprime families of Fibonacci pseudoprimes: p(p+2), p(2p−1), and p(2p+3), under explicit congruence conditions on the prime p. We determine exactly which members of these families satisfy the stronger Frobenius–Fibonacci pseudoprime conditions. If π(q) denotes the order of the Fibonacci matrix A = [[1,1],[1,0]] modulo the larger prime factor q, then the family p(p+2) contains no Frobenius–Fibonacci pseudoprimes. For q = 2p−1, Frobenius pseudoprimality is equivalent to A^((q−1)/2) = I, or equivalently to (q−1)/π(q) being even. For q = 2p+3, it is equivalent to A^((q−1)/2) = −I, or equivalently to (q−1)/π(q) being odd. Thus the two nonempty families are complementary with respect to whether the Fibonacci-matrix period modulo the larger factor contains the full 2-primary part of q−1. We compare this explicit trichotomy with the general strong-Lucas criteria of Somer and Křížek and exhibit Frobenius members of the 2p−1 family that are not strong Lucas pseudoprimes. A deterministic computation for all relevant primes p < 10^6 gives no exceptions to the classification.