primitive part

Many sequences have the useful divisibility property that F(n) divides F(mn) for positive integers m and n.  Examples of such sequences include the Fibonacci numbers, the Lucas sequences and polynomial sequences such as xⁿ-1 and c(xⁿ-yⁿ).  In fact this last example includes the others because the Fibonacci numbers may be written:

and the Lucas sequences have similar definitions.

When this divisibility property holds we may define the primitive part (or primitive factor) Φ(n) of F(n) as follows:

so that

Here μ is the Möbius function (and the equations above are a special case of the product form of the Möbius inversion formula [Apostol76 Chpt 2]).

Often, but not always, the primitive part of such an F(n) is the maximal divisor of F(n) which is coprime to F(d) for all divisors d of n.  When factoring such sequences, we always first divide them into their primitive parts, and on occassion we are lucky and the primitive parts are prime.  The prime pages' Top Twenty collection has several pages dedicated to such primitive divisors.

Other sequences with similar divisibility properties also have primitive parts.  When defining the primitive parts, additional divisors may be removed from the terms (as in the Lehmer primitive parts) or Aurifeuillian factorizations may need to be acknowledged (as in the Lucas Aurifeuillian primitive parts). 

Related pages (outside of this work)

• The Top 20's Generalized Lucas Primitive Parts
• The Top 20's Lehmer Primitive Parts
• The Top 20's Lucas Aurifeuillian Primitive Parts

References:

Apostol76

T. M. Apostol, Introduction to analytic number theory, Springer-Verlag, New York, NY, 1976.  pp. xii+338, ISBN 0-387-90163-9. MR 55:7892 [QA241.A6]

Riesel94

H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994.  ISBN 0-8176-3743-5. MR 95h:11142 [An excellent reference for those who want to start to program some of these algorithms. Code is provided in Pascal. Previous edition was vol. 57, 1985.]

Stevenhagen87

P. Stevenhagen, "On Aurifeuillian factorizations," Nederl. Akad. Wetensch. Indag. Math., 49:4 (1987) 451--468.  MR 89a:11015

Stewart1976

Stewart, C. L., Primitive divisors of Lucas and Lehmer numbers.  In "Transcendence theory: advances and applications (Proc. Conf., Univ. Cambridge, Cambridge, 1976)," Academic Press, 1977.  London, pp. 79--92, MR0476628

Voutier1998

Voutier, P. M., "Primitive divisors of Lucas and Lehmer sequences. III," Math. Proc. Cambridge Philos. Soc., 123:3 (1998) 407--419.  MR1607969 [From the review: "The main result of this paper is that for any integer n>30 030, the nth element of any Lucas or Lehmer sequence has a primitive divisor."]