Editing Carmichael's theorem

{{Short description|On prime divisors in Fibonacci and Lucas sequences}}
{{about|Carmichael's theorem on [[Fibonacci number]]s and [[Lucas sequence]]s|the recursive definition of the Carmichael function|Carmichael function}}

In [[number theory]], '''Carmichael's theorem''', named after the American mathematician [[Robert Daniel Carmichael|R.&nbsp;D. Carmichael]],
states that, for any nondegenerate [[Lucas sequence]] of the first kind ''U<sub>n</sub>''(''P'',&nbsp;''Q'') with [[relatively prime]] parameters ''P'',&nbsp;''Q'' and positive discriminant, an element ''U<sub>n</sub>'' with ''n''&nbsp;≠&nbsp;1,&nbsp;2,&nbsp;6 has at least one [[prime number|prime]] divisor that does not divide any earlier one except the 12th [[Fibonacci number]] F(12)&nbsp;=&nbsp;''U''<sub>12</sub>(1,&nbsp;−1)&nbsp;=&nbsp;144 and its equivalent ''U''<sub>12</sub>(−1,&nbsp;−1)&nbsp;=&nbsp;−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) [[mathematical proof|proved]] this [[theorem]].  Recently, Yabuta (2001)<ref>{{cite journal |last1=Yabuta |first1=Minoru |title=A simple proof of Carmichael's theorem on primitive divisors |journal=Fibonacci Quarterly |date=2001 |volume=39 |issue=5 |pages=439–443 |doi=10.1080/00150517.2001.12428701 |url=http://www.fq.math.ca/Scanned/39-5/yabuta.pdf |accessdate=4 October 2018}}</ref> gave a simple proof.  Bilu, Hanrot, Voutier and Mignotte (2001)<ref>{{cite journal | first1=Yuri | last1=Bilu | first2=Guillaume | last2=Hanrot | first3=Paul M. | last3=Voutier | first4=Maurice | last4=Mignotte | title=Existence of primitive divisors of Lucas and Lehmer numbers | journal=[[J. Reine Angew. Math.]] | year=2001 | volume=2001 | issue=539 | pages=75–122 | mr=1863855 | doi=10.1515/crll.2001.080 | s2cid=122969549 | url=https://hal.inria.fr/inria-00072867/file/RR-3792.pdf }}  This paper describes sequences in terms of ''P'' and ''D'' (which it calls ''a'' and ''b''); ''Q'' = (''P''<sup>2</sup> − D)/4, so when the paper talks about the sequence with (''a'',&nbsp;''b'') = (1,&nbsp;−7), that means ''P'' = 1, ''Q'' = 2.  The full list of Lucas numbers without a primitive prime divisor is ''n'' = 1, the 23 special cases listed in Table 1, and the general cases listed in Table 3.  (Tables 2 and 4 apply to the related [[Lehmer sequence]].)</ref> extended it to the case of negative discriminants (where it is true for all ''n'' > 30).

==Statement==
Given two relatively prime integers ''P'' and ''Q'', such that <math>D=P^2-4Q>0</math> and {{math|''PQ''&nbsp;≠&nbsp;0}}, let {{math|''U<sub>n</sub>''(''P'',&nbsp;''Q'')}} be the [[Lucas sequence]] of the first kind defined by
:<math>\begin{align}
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) \qquad\mbox{  for }n>1.
\end{align}
</math>

Then, for ''n''&nbsp;≠&nbsp;1,&nbsp;2,&nbsp;6, ''U<sub>n</sub>''(''P'',&nbsp;''Q'') has at least one prime divisor that does not divide any ''U<sub>m</sub>''(''P'',&nbsp;''Q'') with ''m''&nbsp;&lt;&nbsp;''n'', except ''U''<sub>12</sub>(±1,&nbsp;−1)&nbsp;=&nbsp;±F(12)&nbsp;=&nbsp;±144.
Such a prime&nbsp;''p'' is called a ''characteristic factor'' or a ''primitive prime divisor'' of ''U<sub>n</sub>''(''P'',&nbsp;''Q'').
Indeed, Carmichael showed a slightly stronger theorem: For ''n''&nbsp;≠&nbsp;1,&nbsp;2, 6, ''U<sub>n</sub>''(''P'',&nbsp;''Q'') has at least one primitive prime divisor not dividing ''D''<ref>In the definition of a primitive prime divisor&nbsp;''p'', it is often required that ''p'' does not divide the discriminant.</ref> except ''U''<sub>3</sub>(±1,&nbsp;−2)&nbsp;=&nbsp;3, ''U''<sub>5</sub>(±1,&nbsp;−1)&nbsp;=&nbsp;F(5)&nbsp;=&nbsp;5, or ''U''<sub>12</sub>(1,&nbsp;−1)&nbsp;=&nbsp;−''U''<sub>12</sub>(−1,&nbsp;−1)&nbsp;=&nbsp;F(12)&nbsp;=&nbsp;144.

In Camicharel's theorem, ''D'' should be greater than 0; thus the cases ''U''<sub>13</sub>(1,&nbsp;2), ''U''<sub>18</sub>(1,&nbsp;2) and ''U''<sub>30</sub>(1,&nbsp;2), etc. are not included, since in this case ''D''&nbsp;=&nbsp;−7&nbsp;<&nbsp;0.

==Fibonacci and Pell cases==
The only exceptions in Fibonacci case for ''n'' up to 12 are:

:F(1)&nbsp;=&nbsp;1 and F(2)&nbsp;=&nbsp;1, which have no prime divisors
:F(6)&nbsp;=&nbsp;8, whose only prime divisor is 2 (which is F(3))
:F(12)&nbsp;=&nbsp;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, ... {{OEIS|id=A001578}}
Carmichael's [[theorem]] says that every Fibonacci number, apart from the exceptions listed above, has at least one primitive prime divisor.

If ''n''&nbsp;>&thinsp;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, ... {{OEIS|id=A246556}}

==See also==
* [[Zsigmondy's theorem]]

==References==
{{Reflist}}
*{{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 α<sup>''n''</sup>±β<sup>''n''</sup>
 | volume = 15
 | year = 1913
 | jstor = 1967797}}.

[[Category:Fibonacci numbers]]
[[Category:Theorems in number theory]]