Frobenius Classification of Somer's Five Semiprime Lucas Pseudoprime Types

Abstract

Let U(P,Q) be a Lucas sequence with discriminant D = P² − 4Q. Somer identified five semiprime families N = pq of Lucas pseudoprimes, with q = p + 2, 2p − 3, 2p − 1, 2p + 1, or 2p + 3, under prescribed quadratic-character conditions. We determine exactly which members of these five families satisfy the stronger Frobenius pseudoprime congruences. For the four non-twin types, writing M_r = r − (D/r), where (D/r) denotes the Legendre symbol, Somer’s sign patterns yield M_q = 2M_p, and Frobenius pseudoprimality is characterized by a prescribed scalar value of the Lucas companion matrix at the half-exponent M_q/2, together with an explicit scalar obstruction involving Q. In particular, Types 1, 2, and 4 require N | Q − 1, Type 5 requires N | Q² − 1, while Type 3 has no such obstruction. For Q = −1, this gives a universal trichotomy valid for every admissible U(P,−1): Type 1 is never Frobenius, Type 3 is Frobenius exactly when the local matrix coindex is even, and Type 5 exactly when it is odd. For Q = 1, Type 1 is always Frobenius and Types 2–5 are governed by even coindex. A deterministic computation over more than 23.5 million admissible instances with p ≤ 10⁶ found no exceptions to the classification.