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.

  • $\begingroup$ $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$. $\endgroup$ Sep 19, 2014 at 18:20
  • $\begingroup$ @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. $\endgroup$ Sep 19, 2014 at 18:33
  • $\begingroup$ @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$. $\endgroup$
    – user40023
    Sep 19, 2014 at 19:29
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2014 at 21:18
  • $\begingroup$ @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$. $\endgroup$ Sep 19, 2014 at 21:57

2 Answers 2


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

  • 1
    $\begingroup$ 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.) $\endgroup$ Sep 22, 2014 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).$


Your Answer

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