What do we know about Lucas sequence entry points?

Question

For Lucas sequences U_n(P, Q);
X₀=0;
X₁=1;
X_n = P * X_n-1 - Q * X_n-2
Z(n) being the entry point of the sequence, which is the index of the first term divisible by n.
What do we know about z(n)? Is there research out there of z(n) for these sequences? I haven't been able to find anything.

Answer 1

One of the result is that $Z(n)$ must exist and bounded, when $(P,n)=(Q,n)= 1 $ or $n$.

Proof:

If we have this sequence of length $n^2+2$, we group the neighbouring terms in pair, then we have $n^2+1$ pairs.

Consider (mod n), number of possible pairs $(n_1,n_2)$ is $n^2$, $\bigg($$n_1,n_2 \neq 0$ $\biggr)$

by pigeonhole principle, there exists one pair of residues $(n_1,n_2)$, that occurs for at least $\lceil \frac{n^2+1}{n^2} \rceil =2 $ times, say at $(X_{a_1},X_{a_1+1})$ and $(X_{b_1},X_{b_1+1})$, assume that $(X_{a_1},X_{a_1+1})$ is preceding $(X_{b_1},X_{b_1+1})$

As such, this pair will generate the same subsequence with the stated recurrence relation, it must be periodic.

Also, each of the pair is generated with same sub-sequence,

because $X_{n-2}\equiv Q^{-1}[P*X_{n-1}-X_n]\pmod n$, which $Q^{-1} $ exists as long as $(Q,n)=1$.

So let's assume $(Q,n)=1$, then with the above formula, the terms preceding both $n_1,n_2$ are uniquely determined.

Since we know $X_0 \equiv 0 \pmod n$, so we know $X_{b_1-a_1}$ in the sequence is $\equiv 0\pmod n$.

With these preliminaries, we know that $Z(n) \le n^2$.

---

We have assumed that $(Q,n)=1$, now let's consider $n$ is prime only, then the recurrence relation reduces to $X_n\equiv P \cdot X_{n-1} \pmod n$, so $\not\equiv 0 \pmod n$ unless $P \equiv 0 \pmod n$.

Since this does not necessarily hold for prime factors of $Q,P$, by Chinese Remainder Theorem, this does not necessarily holds for all factors of $Q,P$.

Answer 2

There are quite a few things we know but too many to list them all. That being said, I'll mention a few. If $p$ is a prime then what you are referring to is what I call, $\omega(p)$, the rank of apparition of $p$ in the underlying Lucas sequence. Assuming certain criteria being satisfied, some of the things we know given $p$ and a particular Lucas sequence $U_{n}(P, Q)$ are:

(1) $p$ must divide either $U_{n+1}$ or $U_{n-1}$

(2) $\omega(p)$ is a divisor of the index of that "entry point.''

(3) There is no known explicit formula for determining $\omega(p)$ because such is analogous to the computational difficulty of the problem of finding the order of an integer modulo $p$.

(4) If $\omega(p)$ is either $n + 1$ or $n - 1$ then we say that $p$ has ``maximal'' rank of apparition, which is a characteristic only of primes; that is, if $n$ is an integer whose character at the onset unknown, and if you can show that it has maximal rank of apparition, then you then know that $n$ is a prime. (No pseudoprime has maximal rank of apparition.)

(5) If $\omega(m) = 2k,$ then $p$ also has rank of apparition $k$ in the companion sequence, $V_{n}(P, Q)$; If $\omega(m)$ is odd, $p$ does not divide any term of the said companion sequence. For instance, in the sequence of Mersenne numbers, $\omega(65537) = 32$; hence, the prime $65537$ divides the companion sequence of terms $2^{n} + 1$ for the first time at $V_{16}$. On the other hand, the prime $127$ has rank of apparition $7$ in the sequence of Mersenne numbers. Therefore, it is a factor of no number of the form $2^{n} + 1$.

I hope this helps.