2
$\begingroup$

For Lucas sequences Un(P, Q);
X0=0;
X1=1;
Xn = P * Xn-1 - Q * Xn-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.

$\endgroup$
8
  • $\begingroup$ You might find more if you look for "apparition" or "rank of apparition". $\endgroup$ – Gerry Myerson Feb 14 '18 at 6:03
  • $\begingroup$ Have you had that look? $\endgroup$ – Gerry Myerson Feb 15 '18 at 9:49
  • $\begingroup$ yeah. I haven't found anything with regards to that. Could you be more specific with what you mean by apparition? It's a fairly broad term as far as I can tell $\endgroup$ – ukdl123 Feb 16 '18 at 3:12
  • $\begingroup$ Maybe citeseerx.ist.psu.edu/viewdoc/… will be helpful (Marc Renault, The period, rank, and order of the $(a,b)$-Fibonacci sequence mod $m$, Math. Mag. 86, No. 5 (2013) 372--380). Also, sciencedirect.com/science/article/pii/S0362546X05001677 (John Jaroma, On the rank of apparition of composite $N$ in the Lehmer sequences, Nonlinear Analysis: Theory, Methods & Applications 63, Issues 5–7, 30 November–15 December 2005, Pages e1081-e1086). $\endgroup$ – Gerry Myerson Feb 16 '18 at 5:21
  • $\begingroup$ Have a look at those, ukdl? $\endgroup$ – Gerry Myerson Feb 17 '18 at 5:47
0
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ This is really helpful. Do we know anything about the values where Z(n)=n? $\endgroup$ – ukdl123 Feb 14 '18 at 18:04
  • $\begingroup$ I can only give some examples for this, When$ P=1,Q=-1$, which will be the Fibonacci sequence, when n=5, every $F_{5k} \equiv 0 \pmod 5$. And $F_{p-1} \equiv 0 \pmod p$ if and only if $p \equiv +1$ or $-1 \pmod 5$, but $p-1$ is not necessarily its least period, $p$ denotes primes. $\endgroup$ – user376921 Feb 15 '18 at 2:27
  • $\begingroup$ I know the Pisano periods. I was just wondering about other P and Q $\endgroup$ – ukdl123 Feb 15 '18 at 20:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.