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 xn-1 and c(xn-yn).  In fact this last example includes the others because the Fibonacci numbers may be written:

Fibonacci numbers definition

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:

Definition of primitive parts

so that

Definition of primitive parts

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)


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]
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.]
P. Stevenhagen, "On Aurifeuillian factorizations," Nederl. Akad. Wetensch. Indag. Math., 49:4 (1987) 451--468.  MR 89a:11015
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
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."]
Printed from the PrimePages <> © Reginald McLean.