Coprimality of certain linear combinations of Fibonacci numbers (integer coefficients)

Question

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

Answer 1

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