Carmichael's theorem

Statement

Given two coprime integers P and Q, such that D = P 2 − 4 Q > 0 and PQ ≠ 0, let U_n(P,Q) be the Lucas sequence of the first kind defined by

U 0 ( P , Q ) = 0 , U 1 ( P , Q ) = 1 , U n ( P , Q ) = P ⋅ U n − 1 ( P , Q ) − Q ⋅ U n − 2 ( P , Q )  for  n > 1.

Then, for n ≠ 1, 2, 6, U_n(P,Q) has at least one prime divisor that does not divide any U_m(P,Q) with m < n, except U₁₂(1, -1)=F(12)=144, U₁₂(-1, -1)=-F(12)=-144. Such a prime p is called a characteristic factor or a primitive prime divisor of U_n(P,Q). Indeed, Carmichael showed a slightly stronger theorem: For n ≠ 1, 2, 6, U_n(P,Q) has at least one primitive prime divisor not dividing D except U₃(1, -2)=U₃(-1, -2)=3, U₅(1, -1)=U₅(-1, -1)=F(5)=5, U₁₂(1, -1)=F(12)=144, U₁₂(-1, -1)=-F(12)=-144.

Fibonacci and Pell cases

The only exceptions in Fibonacci case for n up to 12 are:

F(1)=1 and F(2)=1, which have no prime divisorsF(6)=8 whose only prime divisor is 2 (which is F(3))F(12)=144 whose only prime divisors are 2 (which is F(3)) and 3 (which is F(4))

The smallest primitive prime divisor of F(n) are

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, ... (sequence A001578 in the OEIS)

Carmichael's theorem says that every Fibonacci number, apart from the exceptions listed above, has at least one primitive prime divisor.

If n > 1, then the nth Pell number has at least one prime divisor that does not divide any earlier Pell number. The smallest primitive prime divisor of nth Pell number are

1, 2, 5, 3, 29, 7, 13, 17, 197, 41, 5741, 11, 33461, 239, 269, 577, 137, 199, 37, 19, 45697, 23, 229, 1153, 1549, 79, 53, 113, 44560482149, 31, 61, 665857, 52734529, 103, 1800193921, 73, 593, 9369319, 389, 241, ... (sequence A246556 in the OEIS)