If $\{a_n\}_{n=1}^\infty$ is a sequence of integers, then the definition of primitive divisor of one of its terms is quite natural:

Def. 1. A prime number $p$ is a primitive divisor of $a_n$ if $p \mid a_n$, but $p \nmid a_1 \cdots a_{n-1}$ (see [1]).

However, when Lucas sequences are involved, usually a different (unnatural, in my opinion) definition is used. Let $\{u_n\}_{n \geq 1}$ be a Lucas sequence of the first kind, with discriminant $\Delta$.

Def. 2. A prime number $p$ is a primitive divisor of $u_n$ if $p \mid u_n$, but $p \nmid \Delta u_1 \cdots u_{n-1}$ (see [2]).

My question is: why include $\Delta$ in Def. 2 matters?

Note that Def. 1 and Def. 2 are actually different. For example, if $\{F_n\}_{n \geq 1}$ is the (Lucas) sequence of Fibonacci numbers, then $5$ is a primitive divisor of $F_5 = 5$, respect Def. 1, but it is not respect to Def. 2, since $\Delta = 5$ for the Fibonacci's.

Thank you in advance for any elucidation.

[1] http://mathworld.wolfram.com/PrimitivePrimeFactor.html

[2] Yu Bilu , G. Hanrot , P. M. Voutier. Existence of primitive divisors of Lucas and Lehmer numbers. J. Reine Angew. Math (2011).

  • $\begingroup$ Since $u_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}=\frac{\alpha^n-\beta^n}{\sqrt{\Delta}}$, neat properties of $u_n$ modulo $p$ tend to fail for $p|\Delta$, since we have to "divide by $0$ modulo $p$". For instance, $u_{n+p^2-1}\equiv u_{n}$ mod $p$ only if $p\nmid \Delta$. $\endgroup$
    – Rodrigo
    Oct 19 '14 at 22:19

For binary linear recurrences such as the Lucas sequences, and for elliptic divisibility sequences, the value/growth of $\text{ord}_p(a_n)$ tends to behave rather differently for primes of bad reduction. What are those? Well, these sequences are associated to algebraic groups, the former to twists of the multiplicative group $\mathbb G_m$ and the latter to elliptic curves $E$, and such groups have primes of bad reduction. For elliptic curves, you can find an explanation in any standard text. For a twist of $\mathbb G_m$, you're talking about something like a Pell equation $X^2-DY^2=1$, whose primes of bad reduction are the primes dividing (the square-free) integer $D$. To take a specific example (generalizing Rodrigo's comment), if we let $r(p)$ be the rank of apparition of a binary linear recurrence (i.e., the smallest $r$ such the $p\mid a_r$), then $r(p)$ divides either $p+1$ or $p-1$ if $p$ is a prime of good reduction.

Having said this, it's usually not that big a deal to discard a finite number of primes when defining primitive prime divisors, since each prime can serve as a primitive prime divisor of at most one element of the sequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy