Carmichael's Theorem

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 12th Fibonacci number F(12) = ''U''₁₂(1, −1) = 144 and its equivalent ''U''₁₂(−1, −1) = −144.

In particular, for ''n'' greater than 12, the ''n''th 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 integers ''P'' and ''Q'', such that $D=P^2-4Q>0$ and , let be the Lucas sequence of the first kind defined by
:$\begin U_0(P,Q)&=0, \\ U_1(P,Q)&=1, \\ U_n(P,Q)&=P\cdot U_(P,Q)-Q\cdot U_(P,Q) \qquad\mboxn>1. \end$

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''In the definition of a primitive prime divisor ''p'', it is often required that ''p'' does not divide the discriminant. 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.

Note that ''D'' should be greater than 0; thus the cases ''U''₁₃(1, 2), ''U''₁₈(1, 2) and ''U''₃₀(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, ...
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 ''n''th Pell number has at least one prime divisor that does not divide any earlier Pell number. The smallest primitive prime divisor of ''n''th 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, ...

See also

* Zsigmondy's theorem

References

*{{citation
, last = Carmichael , first = R. D. , author-link = Robert Daniel Carmichael
, doi = 10.2307/1967797
, issue = 1/4
, journal = Annals of Mathematics
, pages = 30–70
, title = On the numerical factors of the arithmetic forms α^''n''±β^''n''
, volume = 15
, year = 1913
, jstor = 1967797.

Fibonacci numbers
Theorems in number theory