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 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

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 OEIS)

See also

References

This article is issued from Wikipedia - version of the Tuesday, October 13, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.