Carmichael's theorem

<h2 id="statement">Statement</h2>
Given two relatively prime integers P and Q, such that 
 
 
 
 D
 =
 
 P
 
 2
 
 
 −
 4
 Q
 >
 0
 
 
 {\displaystyle D=P^{2}-4Q>0}
 
 and PQ ≠ 0, let Un(P, Q) be the <a href="/facts/Lucas_sequence/kceqhe6X">Lucas sequence</a> of the first kind defined by

U
                  
                    0
                  
                
                (
                P
                ,
                Q
                )
              
              
                
                =
                0
                ,
              
            
            
              
                
                  U
                  
                    1
                  
                
                (
                P
                ,
                Q
                )
              
              
                
                =
                1
                ,
              
            
            
              
                
                  U
                  
                    n
                  
                
                (
                P
                ,
                Q
                )
              
              
                
                =
                P
                ⋅
                
                  U
                  
                    n
                    −
                    1
                  
                
                (
                P
                ,
                Q
                )
                −
                Q
                ⋅
                
                  U
                  
                    n
                    −
                    2
                  
                
                (
                P
                ,
                Q
                )
                
                
                  
                     for 
                  
                
                n
                >
                1.
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}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{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.
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<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> except U3(±1, −2) = 3, U5(±1, −1) = F(5) = 5, or U12(1, −1) = −U12(−1, −1) = F(12) = 144.
In Camicharel's theorem, D should be greater than 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.

<h2 id="fibonacci-and-pell-cases">Fibonacci and Pell cases</h2>
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 <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>)
Carmichael's <a href="/facts/Theorem/f2Pe1FMD">theorem</a> says that every Fibonacci number, apart from the exceptions listed above, has at least one primitive prime divisor.
If n > 1, then the nth <a href="/facts/Pell_number/VMu7fXmx">Pell number</a> 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 <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>)
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Zsigmondy%27s_theorem/MsrsoSa2">Zsigmondy's theorem</a></li></ul>

<ul><li><a href="/facts/Robert_Daniel_Carmichael/tz4d4Dx6">Carmichael, R. D.</a> (1913), "On the numerical factors of the arithmetic forms αn±βn", Annals of Mathematics, 15 (1/4): 30–70, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1967797">10.2307/1967797</a>, <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1967797">1967797</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Yabuta, Minoru (2001). "A simple proof of Carmichael's theorem on primitive divisors" (PDF). Fibonacci Quarterly. 39 (5): 439–443. doi:10.1080/00150517.2001.12428701. Retrieved 4 October 2018. <a href="http://www.fq.math.ca/Scanned/39-5/yabuta.pdf" target="_blank">http://www.fq.math.ca/Scanned/39-5/yabuta.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "Existence of primitive divisors of Lucas and Lehmer numbers" (PDF). J. Reine Angew. Math. 2001 (539): 75–122. doi:10.1515/crll.2001.080. MR 1863855. S2CID 122969549. This paper describes sequences in terms of P and D (which it calls a and b); Q = (P2 − D)/4, so when the paper talks about the sequence with (a, b) = (1, −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.) <a href="https://hal.inria.fr/inria-00072867/file/RR-3792.pdf" target="_blank">https://hal.inria.fr/inria-00072867/file/RR-3792.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">In the definition of a primitive prime divisor p, it is often required that p does not divide the discriminant. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
</ol>

Carmichael's theorem open-in-new

Carmichael's theorem