Carmichael's theorem
- This article refers to Carmichael's theorem about Fibonacci numbers. Carmichael's theorem may also refer to the recursive definition of the Carmichael function.
Carmichael's theorem, named after the American mathematician R.D. Carmichael, states that 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.
The only exceptions 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))
If a prime p is a divisor of F(n) that does not divide any F(m) with m < n, then p is called a characteristic factor or a primitive prime divisor of F(n). 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.
The theorem can be generalized from Fibonacci numbers to other Lucas sequences. For example, 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
- 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
References
- Carmichael, R. D. (1913), "On the numerical factors of the arithmetic forms αn±βn", 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= - Yabuta, M. (2001), "A simple proof of Carmichael's theorem on primitive divisors" (PDF), Fibonacci Quarterly, 39: 439–443.