5
$\begingroup$

Let $G_k(m,n)=m\,F_k+n\,F_{k-1}$, where $k,m,n$ are any integers and $(F_k)_{k\in\mathbb{Z}}$ is the extended Fibonacci sequence defined by $F_0=0,F_1=1,F_{k+2} = F_{k+1}+F_k$ for all $k\in\mathbb{Z}.$

Conjecture:

There exist nonzero $(m,n)$ for which $G_k(m,n)$ and $G_{k+1}(m,n)-1$ are coprime for all $k$.

Some small candidate examples are $(m,n) = (6, 12), (12, 84), (18, 6), (18, 36), (24, 18), (30, 90).$ E.g., computations show that $G_k(6,12)$ and $G_{k+1}(6,12)-1$ are coprime for all $k\in [-10^6,10^6]$.

(I suspect that there are infinitely many such pairs $(m,n)$. It would be very interesting to know how to determine them, other than as candidates obtained by testing a large range of $k$-values.)

The conjecture might be proved by somehow using the known fact that any three consecutive Fibonacci numbers $F_{k+1},F_k,F_{k-1}$ are pairwise coprime, but I don't see how to proceed with this.

Question: Is the above conjecture correct? (Proof? Disproof? References?) If so, how can the pairs $(m,n)$ be determined?

Motivation: The conjecture implies a negative answer to a recently asked question; viz., it implies that there exist rational $x$ such that iterating $f:x\mapsto{a+b\over a+1}$(with $x={a\over b}$ in least terms) yields a sequence of iterates $(x,f(x),f(f(x)),\ldots)$ converging to $\varphi={1+\sqrt{5}\over 2}$ (the Golden Mean). This is because it can be shown that if $(m,n)$ is any one of the conjectured pairs, then for $x={m-1\over n}$ the $k$th iterate is $f^k({m-1\over n})={G_{k+1}(m,n)-1\over G_k(m,n)}$, which converges to $\varphi$ due to the fact that ${F_{k+1}\over F_k}\to \varphi.$

More generally, for the parametric family of maps $f_c:x\mapsto{a+b\over a+c}$(with $x={a\over b}$ in least terms), $c\in\mathbb{Z},$ we find ${f_c}^k({m-c\over n})={G_{k+1}(m,n)-c\over G_k(m,n)}\to\varphi\ $ if $(m,n)$ is any one of the pairs in the following conjecture:

Conjecture:

For any integer $c$, there exist nonzero $(m,n)$ for which $G_k(m,n)$ and $G_{k+1}(m,n)-c$ are coprime for all $k$.

$\endgroup$
2
  • $\begingroup$ I asked a related question at math.stackexchange.com/q/3437651/718671. Hopefully someone is able to finish or advance my answer there. $\endgroup$
    – ViHdzP
    Nov 16 '19 at 6:07
  • $\begingroup$ I made a huge edit to my previous answer. You should check it out. $\endgroup$
    – ViHdzP
    Nov 16 '19 at 23:43
1
$\begingroup$

I couldn’t prove your generalized conjecture, but I have an algorithm to determine if a given triple $(m,n,c)$ satisfies $$\gcd\left(G_k(m,n),G_{k+1}(m,n)-c\right)=1$$ for all $k$. I’d like to give huge thanks to user @aman. Were it not for their answer in my spin-off question Congruences of consecutive Fibonacci numbers, I wouldn’t have been able to give this answer.

Consider the expression $$\gcd\left(G_{k-r}(m,n)-cF_r,G_{k-r+1}(m,n)-cF_{r+1}\right).\label{1}\tag{1}$$ By using that $\gcd(a,b)=\gcd(a,a+b)$, we can deduce that this equals $$\gcd\left(G_{k-r+1}(m,n)-cF_{r+1},G_{k-r+2}(m,n)-cF_{r+2}\right).$$ By a trivial two-sided induction, $\eqref{1}$ attains the same value for every integer $r$. In particular, setting $r=0$, $r=k$, we get $$\gcd\left(G_k(m,n),G_{k+1}(m,n)-c\right)=\gcd\left(G_0(m,n)-cF_{k},G_1(m,n)-cF_{k+1}\right)=\gcd\left(cF_k-n,cF_{k+1}-m\right).$$ In other words, we just want to prove whether there exist integers $m$, $n$, such that for no prime $p$, there exists a solution to $$\label{2}\tag{2}cF_{k+1}\equiv m\pmod{p},\\cF_k\equiv n\pmod{p}.$$

This next part is due to @aman (although heavily adapted). We consider the equation $$c^2F_{k-r}\equiv(-1)^r\left(cF_{r+1}n-cF_rm\right)\pmod{p}.\label{3}\tag{3}$$ As we’ve already shown, this holds for $r=-1$, $r=0$. Again, by a trivial two-sided induction, using only that $$a\equiv b\pmod{p},\quad c\equiv d\pmod{p}\Rightarrow a\pm c\equiv b\pm d\pmod{p},$$ we can prove that $\eqref{3}$ holds for every integer $r$. In particular, for $r=k-1$, $$c^2\equiv (-1)^{k-1}\left(cF_kn-cF_{k-1}m\right)\equiv(-1)^{k-1}\left(n^2-(m-n)m\right)\equiv(-1)^{k-1}\left(n^2+mn-m^2\right)\pmod{p}.$$ The only candidate primes for $\eqref{2}$ are therefore those that satisfy either $$p\mid m^2-mn-n^2-c^2\text{ or }p\mid m^2-mn-n^2+c^2.$$ Therefore, to check a triple $(m,n,c)$, it suffices to just check the Pisano periods modulo each of these primes.

Here are some examples of triples for $1\leq c\leq100$.

$(6, 12,1)$, $(3, 21,2)$, $(4, 8,3)$, $(3, 6,4)$, $(12, 24,5)$, $(10, 15,6)$, $(12, 54,7)$, $(42, 54,7)$, $(3, 36,8)$, $(2, 4,9)$, $(3, 9,10)$, $(12, 24,11)$, $(1, 2,12)$, $(6, 12,13)$, $(6, 27,14)$, $(4, 8,15)$, $(9, 18,16)$, $(6, 42,17)$, $(6, 7,18)$, $(6, 12,19)$, $(3, 6,20)$, $(2, 4,21)$, $(3, 21,22)$, $(6, 12,23)$, $(1, 7,24)$, $(6, 18,25)$, $(18, 21,26)$, $(8, 16,27)$, $(21, 27,28)$, $(6, 12,29)$, $(1, 2,30)$, $(66, 132,31)$, $(9, 18,32)$, $(2, 4,33)$, $(3, 36,34)$, $(12, 18,35)$, $(1, 2,36)$, $(6, 12,37)$, $(6, 27,38)$, $(16, 22,39)$, $(15, 21,40)$, $(18, 36,41)$, $(11, 12,42)$, $(18, 36,43)$, $(9, 18,44)$, $(4, 8,45)$, $(21, 42,46)$, $(6, 12,47)$, $(1, 2,48)$, $(6, 12,49)$, $(3, 15,50)$, $(2, 4,51)$, $(27, 39,52)$, $(12, 24,53)$, $(6, 7,54)$, $(6, 18,55)$, $(3, 6,56)$, $(4, 18,57)$, $(15, 60,58)$, $(24, 48,59)$, $(4, 5,60)$, $(12, 24,61)$, $(9, 33,62)$, $(2, 4,63)$, $(15, 45,64)$, $(6, 24,65)$, $(2, 9,66)$, $(12, 24,67)$, $(6, 27,68)$, $(10, 20,69)$, $(6, 9,70)$, $(24, 48,71)$, $(1, 2,72)$, $(18, 36,73)$, $(15, 45,74)$, $(2, 6,75)$, $(3, 21,76)$, $(12, 24,77)$, $(9, 13,78)$, $(12, 24,79)$, $(9, 12,80)$, $(4, 8,81)$, $(3, 21,82)$, $(18, 66,83)$, $(2, 9,84)$, $(18, 36,85)$, $(27, 54,86)$, $(4, 8,87)$, $(15, 45,88)$, $(6, 12,89)$, $(1, 2,90)$, $(6, 12,91)$, $(33, 36,92)$, $(2, 4,93)$, $(15, 45,94)$, $(6, 36,95)$, $(5, 10,96)$, $(48, 66,97)$, $(3, 21,98)$, $(14, 28,99)$, $(3, 9,100)$.

$\endgroup$
4
  • $\begingroup$ Nice work! For various $c$-values I had found numerous candidate pairs $(m,n)$ such that $(G_k, G_{k+1}-c)$ remained coprime for $1\le k\le 1000$; but when I programmed your algorithm it found only a subset of those. Much to my satisfaction, in all cases that I've re-examined, increasing the range of $k$-values (e.g. to $1\le k\le 10000$ or more) eliminates every candidate not found by your algorithm. $\endgroup$
    – r.e.s.
    Nov 17 '19 at 6:43
  • $\begingroup$ But ...your algorithm applies only when $(m,n,c)$ is such that $m^2 - mn - n^2 \pm c^2 \ne 0$? $\endgroup$
    – r.e.s.
    Nov 17 '19 at 17:22
  • $\begingroup$ @r.e.s. If $m^2-mn-n^2\pm c^2=0$, $m$ and $n$ need to be $c$ times some pair of consecutive Fibonacci numbers, and these will fail immediately. I’ll add the proof of this to the answer shortly. $\endgroup$
    – ViHdzP
    Nov 17 '19 at 17:38
  • $\begingroup$ I’m 99% sure that you can take the method from here to prove this. But I haven’t had time to check, so I’ll write it up later on. $\endgroup$
    – ViHdzP
    Nov 18 '19 at 6:08

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.