# Carmichael's theorem

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 Un(P,Q) with relatively prime parameters P, Q and positive discriminant, an element Un with n ≠ 1, 2, 6 has at least one prime divisor that does not divide any earlier one except the 12th Fibonacci number F(12)=U12(1, -1)=144 and its equivalent U12(-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)[1] gave a simple proof.

Contents 1 Statement 2 Fibonacci and Pell cases 3 See also 4 References Statement Given two coprime integers P and Q, such that {displaystyle D=P^{2}-4Q>0} and PQ ≠ 0, let Un(P,Q) be the Lucas sequence of the first kind defined by {displaystyle {begin{aligned}U_{0}(P,Q)&=0,\U_{1}(P,Q)&=1,\U_{n}(P,Q)&=Pcdot U_{n-1}(P,Q)-Qcdot U_{n-2}(P,Q)qquad {mbox{ for }}n>1.end{aligned}}} Then, for n ≠ 1, 2, 6, Un(P,Q) has at least one prime divisor that does not divide any Um(P,Q) with m < n, except U12(1, -1)=F(12)=144, U12(-1, -1)=-F(12)=-144. Such a prime p is called a characteristic factor or a primitive prime divisor of Un(P,Q). Indeed, Carmichael showed a slightly stronger theorem: For n ≠ 1, 2, 6, Un(P,Q) has at least one primitive prime divisor not dividing D[2] except U3(1, -2)=U3(-1, -2)=3, U5(1, -1)=U5(-1, -1)=F(5)=5, U12(1, -1)=F(12)=144, U12(-1, -1)=-F(12)=-144. Note that D should be > 0, thus the cases U13(1, 2), U18(1, 2) and U30(1, 2), etc. are not included, since in this case D = −7 < 0. 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 ^ Yabuta, M (2001). "A simple proof of Carmichael's theorem on primitive divisors" (PDF). Fibonacci Quarterly. 39: 439–443. Retrieved 4 October 2018. ^ In the definition of a primitive prime divisor p, it is often required that p does not divide the discriminant. 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. Categories: Fibonacci numbersTheorems in number theory

Si quieres conocer otros artículos parecidos a Carmichael's theorem puedes visitar la categoría Fibonacci numbers.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información