Lehmer numbers with at least 2 primitive divisors

In 1878, Lucas [16] investigated the sequences ℓn∞ n=0 where ℓn=an-b na-b, αβ and α + β are coprime integers, and where β/α is not a root of unity. Lucas sequences are divisibility sequences; if m|n, then ℓm|ℓ n, and more generally, gcd(ℓm, ℓ n) = ℓgcd(m,n ) for all positive integers m and n. Matijasevic utilised this divisibility property of Lucas sequences in order to resolve Hilbert's 10th problem.;We let k=k&parl0;abmax &cubl0;&parl0;a-b&parr0;2, a+b2&cubr0;&parr0; , h= 1ifk≡1 mod4 ,2otherwise, where k(αβ max{(α-β) 2, (α+β)2}) is the squarefree kernel of αβ max{(α-β)2, (α+β)2}. On the one hand, building on the work of Schinzel [24], we prove that if n > 4, n ≠ 6, n/(ηκ) is an odd integer, and the triple (n, α, β), in case (α-β)2 > 0, is not equivalent to a triple ( n, α, β) from an explicit table, then the nth Lehmer number un has at least two primitive divisors. Moreover, we prove that if n ≥ 1.2×10 10, and n/(ηκ) is an odd integer, then the nth Lehmer number un has at least two primitive divisors. On the other hand, building on the work of Stewart [30], we prove that there are only finitely many triples ( n, α, β), where n > 6, n 6 ≠ 12, and n/(ηκ) is an odd integer, such that the nth Lehmer number un has less than two primitive divisors, and that these triples may be explicitly determined. We determine all of these triples (n, α, β) up to equivalence explicitly when 6 < n ≤ 30, n ≠ 12, and n/(ηκ) is an odd integer, and we tabulate the triples (n, α, β) we discovered, up to equivalence, for 30 < n ≤ 500. Finally, we show that the conditions n > 6, n ≠ 12, are best possible, subject to the truth of two plausible conjectures.;In 1930, Lehmer [15] introduced the sequences un∞ n=0 where un=an-bn aen -ben , en= 1,ifn≡ 1mod2 ;2,if n≡0mod 2; αβ and (α+β)2 are coprime integers, and where β/α is not a root of unity. The sequences un∞ n=0 are known as Lehmer sequences, and the terms of these sequences are known as Lehmer numbers. Lehmer showed that his sequences had similar divisibility properties to those of Lucas sequences, and he used them to extend the Lucas test for primality. We define a prime divisor p of un to be a primitive divisor of un if p does not divide a2-b2 2u3˙˙˙un-1. Note that in the list of prime factors of the first n - 1 terms of the sequence un∞ n=0, a primitive divisor of un is a new prime factor.