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

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

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

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

• 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. – r.e.s. Nov 17 '19 at 6:43
• But ...your algorithm applies only when $(m,n,c)$ is such that $m^2 - mn - n^2 \pm c^2 \ne 0$? – r.e.s. Nov 17 '19 at 17:22
• @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. – ViHdzP Nov 17 '19 at 17:38
• 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. – ViHdzP Nov 18 '19 at 6:08