# Strong divisibility of Lucas sequences

Let $a$ and $b$ be relatively prime integers and let $u_n$ be their associate Lucas sequence, i.e., the second order linear recurrence sequence satisfying $u_0 = 0$, $u_1 = 1$ and $u_{n+2} = au_{n+1} + bu_n$, for each nonnegative integer $n$.

It is well know that $(u_n)_{n=0}^\infty$ is a strong divisibility sequence, i.e., it holds $$(\bullet) \quad \gcd(u_m, u_n) = u_{\gcd(m,n)} ,$$ for all the integers $m,n \geq 0$ (put $\gcd(0,0) := 0$). This in turn implies that $$(\star) \quad m \mid n \Rightarrow u_m \mid u_n ,$$ for all the integers $m,n \geq 0$.

My question is: Are there some nice hypothesis under which also the reverse implication holds in ($\star$) ?

Note that from ($\bullet$), we get $$u_m \mid u_n \Rightarrow u_m = \gcd(u_m, u_n) = u_{\gcd(m,n)} ,$$ so if $(u_n)_{n=0}^\infty$ is injective then $m = \gcd(m,n)$ and thus $m \mid n$. So my question can be also answered if one gets some nice hypothesis under which $(u_n)_{n=0}^\infty$ is injective.

Thank you in advance for any suggestion.

• $u_n$ grows exponentially (except in trivial cases) so you get eventual injectivity. That's the best you can expect, e.g. $a=b=1$ (Fibonacci) has $u_2=u_1$. Sep 19 '14 at 18:20
• @FelipeVoloch Maybe better than abstract "eventual injectivity" would be an effective bound, in terms of $a$ and $b$, for when injectivity starts. This should be feasible. Of course, for higher order linear recurrences with many largest eigenvalues, it's much harder. Sep 19 '14 at 18:33
• @FelipeVoloch $u_n$ do not grows exponentially in many non trivial cases, for example: let $a = 2A$ and $b = 1 - 2A^2$, for some integer $A \neq 0$. Then the roots $\alpha,\beta$ of the characteristic polynomial $x^2 - ax - b$ are such that $|\alpha| = |\beta| = 1$.
– user40023
Sep 19 '14 at 19:29
• What is the exact question? Is it: "When does a sequence of integers satisfy $u_m|u_n \Rightarrow m|n?$" Certainly one can set $u_1=c$ at the expense of making everything a multiple of $c$ but not of $c^2$. Or is it "When does a sequence given by a linear recurrence with constant coefficients satisfy $u_m|u_n \Rightarrow m|n?$ If $u_i$ is one such, then $u_i^t$ is another, although with a higher order recurrence. Sep 19 '14 at 21:18
• @Fry If $|\alpha| = |\beta| = 1$, then $|b| = |\alpha||\beta| = 1$ and for the roots to be complex $a^2 +4b <0$ so $b=-1, |a| < 2$. Sep 19 '14 at 21:57

I found a method to solve this problem. We recall the primitive prime factor theorem

Theorem 2.3.1 (Florian Luca, Effective methods for diophantine equations) If $k \notin \{1,2,3,4,6\}$, then $u_k$ has a primitive prime factor except when $(a,\Delta,k)$, where $\Delta = a^2 + 4b$, is one of the following triples:

$$(1, 5, 5), (1, -7, 5), (2, -40, 5), (1, -11,5), (1, -15, 5), (12, -76, 5), (12, -1364, 5),$$ $$(1, -7, 7), (1, -19, 7),$$ $$(2, -24, 8), (1, -7, 8),$$ $$(2,-8,10), (5, -3, 10),$$ $$(1, 5, 12), (1, -7, 12), (1, -11, 12), (2, -56, 12), (1, -15, 12), (1, -19, 12),$$ $$(1, -7, 13),$$ $$(1, -7, 18),$$ $$(1, -7, 30).$$

Now, let $m$ and $n$ be positive integers such that $u_m \mid u_n$ but $m \nmid n$. From $(\bullet)$ we have that $$u_m = \gcd(u_m, u_n) = u_d ,$$ where $d = \gcd(m,n) < m$. It follows that $u_m$ has not a primitive prime factor. From Theorem 2.3.1 then or $m \in \{1,2,3,4,6\}$ or $(a,\Delta,m)$ is one of the triples listed above. In each of these cases, we can (patiently) check if actually there exist or not a divisor $d$ of $m$ such that $u_m = u_d$.

• Nice to know this result. I found this link for the book: math.dartmouth.edu/~m105f12/lucaHungary1.pdf Luca gives the history which is kind of interesting and stretches from 1892 (for integer roots) to 2001 (for complex roots.) Sep 22 '14 at 22:18

Here is a conjectured answer along with a few results and observations.

• The first few values are $u_{{1}}=1,u_{{2}}=a,u_{{3}}={a}^{2}+b,u_{{4}}={a}^{3}+2\,ab,$$u_{{5}}={ a}^{4}+3\,{a}^{2}b+{b}^{2},u_{{6}}={a}^{5}+4\,{a}^{3}b+3\,a{b}^{2} • In general,$$u_{n+1}=\sum_0^{\lfloor n/2 \rfloor}\binom{n-i}{i}a^{n-2i}b^{i}$$The desired divisibility condition fails in the following cases. I conjecture that these are the only exceptions • When a=0 we have u_4 \mid u_6 as both are zero. • When a=\pm 1 we have u_2=a \mid u_3. • When b=-a^2 \pm 1 we have u_3=\pm 1 \mid u_4 • When b=\frac{-a^2 \pm 1}{2} We have u_4 \mid u_6 since u_4=a(a^2+2b)=\pm u_2 • u_{2i}=u_i\left(u_{i+1}+bu_{i-1}\right) and in general, u_{i+j}=u_iu_{j+1}+bu_{i-1}u_j As noted, since \gcd(u_m,u_n)=u_{\gcd(m,n)}, the only way to have u_m \mid u_n and yet not have m \mid n is to have |u_m|=|u_k| where k=\gcd(m,n) \lt m., Writing m=jk this becomes$$|u_{jk}|=|u_{k}|$$• Since u_n(-a,b)=\pm u_n(a,b) we may restrict attention to a \ge 2. • The most promising case would seem to be |u_{2k}|=|u_k| Where we would need v_k=\frac{u_{2k}}{u_k}=u_{k+1}+bu_{k-1} to be \pm 1. If we define v_0=2 then these values 2,a,a^2+2b,a^3+3ab,\cdots also satisfy v_{k+2}=av_{k+1}+bv_k and have v_i \mid v_{i\ell} for odd \ell. In particular |v_k|=1 is impossible (for a \ge 2) when k has an odd divisor. This leaves only powers of 2. An example:$$v_8={a}^{8}+8\,{a}^{6}b+20\,{a}^{4}{b}^{2}+16\,{a}^{2}{b}^{3}+2\,{b}^{4}.$$An integer solution of$v_8=\pm 1$would require$a$to be a divisor of$b^4 \pm 1$• Further thoughts on$v_k=\pm 1$: Certainly the odd$k$are ruled out by$v_1=a\mid v_k.$When$v_2=a^2+2b$has$v_2=\pm 1$one could examine the case that also$v_{2k}=\pm 1$for some prime$k.$• Although I can believe that$k \mapsto |u_k|$is eventually (and perhaps very quickly) injective, I'm not sure that the growth rate alone is enough. In the case$a=1,b=-2,$the indices$197 \le i \le 214$in order of increasing$|u_i|$are$201, 198, 214, 197, 199, 200, 204, 202, 203, 206, 209, 205, 207, 208, 211, 210, 212, 213$Also, for$a=5,b=-7$,$u_{293} \lt u_{289}.$On the other hand, an exception would need to be$|u_{jk}|=|u_k|$for$j \ge 3$or$|u_{2k}|=|u_{k}|$for$k$a power of two. • Here are some (maybe all) sporadic cases of$u_n(1,b)=\pm 1:u_5(1,-2),u_{13}(1,-2),u_5(1,-3),u_7(1,-5).\$