Carmichael's theorem

This article is about Carmichael's theorem on Fibonacci numbers and Lucas sequences. For the recursive definition of the Carmichael function, see Carmichael function.

In number theory, Carmichael's theorem, named after the American mathematician R.D. Carmichael, states that, for any nondegenerate Lucas sequence of the first kind U_n(P,Q) with relatively prime parameters P, Q and positive discriminant, an element U_n with n ≠ 1, 2, 6 has at least one prime divisor that does not divide any earlier one except the 12nd Fibonacci number F(12)=U₁₂(1, -1)=144 and its equivalent U₁₂(-1, -1)=-144.

In particular, for n greater than 12, the nth Fibonacci number F(n) has at least one prime divisor that does not divide any earlier Fibonacci number.

Carmichael (1913, Theorem 21) proved this theorem. Recently, Yabuta (2001) gave a simple proof.

Statement

Given two relatively prime integer parameters P and Q, let U_n(P,Q) be the Lucas sequence of the first kind:

${\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{ for }}n>1.\end{aligned}}$

Assume that the roots a, b of the characteristic equation

$x^{2}-Px+Q=0\,$

are real and a/b is not a root of unity. Equivalently, assume that $D=P^{2}-4Q>0$ and PQ≠ 0.

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 divisors

F(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)

See also

• Zsigmondy's theorem

References

• Carmichael, R. D. (1913), "On the numerical factors of the arithmetic forms αⁿ±βⁿ", Annals of Mathematics, 15 (1/4): 30–70, doi:10.2307/1967797, JSTOR 1967797.
• Knott, R., Fibonacci numbers and special prime factors, Fibonacci Numbers and the Golden Section {{citation}}: External link in |publisher= (help).
• Yabuta, M. (2001), "A simple proof of Carmichael's theorem on primitive divisors" (PDF), Fibonacci Quarterly, 39: 439–443.