Let $u,\bar u$ be the roots of the equation $x^2-x-1=0$ (the characteristic equation of the sequence). Since every prime divisor of $m$ has $5$ as a quadratic residue, if we fix $p$, we can regard $u,\bar u$ as residues $\pmod p$, and carry out the computations in this manner. The general term of the sequence is $x_n=\alpha u^n+\beta \bar u^n$ (where I changed the notations a bit and took $x_0=a,x_1=b$), and we must show that we can pick $\alpha,\beta\pmod p$ s.t. $\alpha u^n+\beta \bar u^n\ne 0,\ \forall n$ in $\mathbb Z_p$. We can do this by taking $au\equiv b\pmod p$, which translates (after doing the computations) to $\beta\equiv 0\pmod p$.

Quote: Since every prime divisor of m has 5 as a quadratic residue, if we fix p, we can regard $u,\bar u$ as residues $\pmod p$, and carry out the computations in this manner. I' m beginner in "mathematic english" Can you explain me what does "quadratic residue" mean ?

jak sama nazwa wskazuje, jest to reszta kwadratowa

Can you give me a more clearly solution ,Grobber ?

Nice solution Grobber, it is also what I had!

It is a very nice solution! One can make it a little bit more elementary. If we take $ x = 2k + 1 + m $ then $ x^{2} - 2x - 4 \equiv (2k+1)^{2} - 2(2k+1) - 4 = 4k^{2} + 4k + 1 - 4k - 2 - 4 = 4k^{2}-5 = m \equiv 0 \ (mod \ m) $. Therefore because of $ x $ being even we can take $ y = x/2 $ and then $ x^{2} - 2x - 4 = 4(y^{2} - y - 1) \equiv 0 \ (mod \ m) $, and because $ m $ is odd, we get that $ y^{2} - y - 1 \equiv 0 \ (mod \ m) $. Also we have $ gcd(y,m)= 1 $, because $ 2y \equiv 2k+1 \ (mod \ m) $, so $ 2(2k-1)y \equiv 4k^{2} - 1 \equiv 4 \ (mod \ m) $, and $ m $ is odd. Therefore also $ y^{n} $ is co-prime to $ m $. Now if we take $ x_{1} = y $, $ x_{2} = y^{2} $ and define $ x_{n} $ by recursion $ x_{n+2} = x_{n+1} + x_{n} $, then of course $ x_{n+2} \equiv x_{n+1} + x_{n} \ (mod \ m) $, but also because of $ y $ satisfying $ y^{2} - y - 1 \equiv 0 \ (mod \ m) $, we get that $ y^{n+2} \equiv y^{n+1} + y^{n} \ (mod \ m) $, and by induction one can show that $ x_{n} \equiv y^{n} \ (mod \ m) $ for every $ n \geqslant 0 $. Now, we have seen that $ y^{n} $ is co-prime to $ m $, so $ x_{n} $ is also co-prime to $ n $.

Incidentally, this was also problem 6 of the 2nd TST of Taiwan 2005.

Suppose $k$ is not a multiple of 5, then let prime factorization $m=p_1^{a_1}p_2^{a_2}...p_r^{a_r}$. Define the Fibonacci sequence to be $F_0=1, F_1=1, F_n=F_{n-1}+F_{n-2}$. By Binet's formula, $F_n = \frac{1}{\sqrt{5}} \left ( \left (\frac{1+\sqrt{5}}{2} \right )^{n+1} - \left ( \frac{1-\sqrt{5}}{2} \right )^{n+1} \right )$ Lemma 1: $x^2 = q^2(\mod p)$ has at two solutions $x$ modulo $p^a$ if $(p, q)=1$ and $p$ is odd prime. Proof: It factors to $(x+q)(x-q)=0(\mod p)$. then $p$ divides either $x+q$ or $x-q$ the desired lemma follows. Hence from Lemma 1 we know $\sqrt{5} = \pm 2k (mod p_i)$ for $i=1, 2, ..., r$ since we know $p_i$ is not 2 or 5. Lemma 2: $F_n \neq \left ( \frac{1+\sqrt{5}}{2} \right)F_{n-1} (\mod p_i)$. Proof: Assume it's true, then we know $\sqrt{5}=\pm 2k$ and it's relatively prime to $p_i$ so WLOG we let it be $\sqrt{5}=2k$ we substitute $F_n$ and $F_{n+1}$ and simplify we have $(1-2k)^n (4k) = 0(\mod p_i)$. but if $p_i|1-2k$ then $p_i|m+(1+2k)(1-2k)$ => $p_i | 4$=> $p_i=2$ so contradiction. If $p_i | 4k$ then $p_i |5$ also contradiction. The desired lemma follows(you could just make a simple argument with limits, but I'm not sure how rigorous that is) Now let $a=2k^2-k-3$ $a = -\frac{1+2k}{2} (\mod m)$ and so $a$ is relatively prime to $m$ since $4k^2-5 - (2k+1)(2k-1) = -4$ and $(4, 4k^2-5)=1$ $b=1$ . Now $x_n=F_{n-1}a + F_{n})b=-F_{n-1} \phi + F_n(\mod p_i)$ and it's never 0 relatively prime to all $p_i$ so relatively prime to $m$ as desired. If $k$ is a multiple of 5 it's not big deal, as 5 is the largest power of 5 that divides m so $m=5 p_1^{a_1} p_2^{a_2}...p_r^{a_r}$ so we can just say $a=2k^2-k-3$ $a = 2(\mod 5)$ and $a = -\frac{1+2k}{2} (\mod \frac{m}{5})$ $b=1$, and we know $x_n$ is relatively prime to all $p_i$ and is relatively prime to 5 (modulo 5 $x_n$ sequence is 2, 1, 3, 4, 2, 1, 3, 4....). So $x_n$ and $m$ are relatively prime too. QED

Is Leva 1980's solution is true? I could not translate to any of $a$ or $b$. Abdurashid

grobber wrote: The general term of the sequence is $ x_n = \alpha u^n + \beta \bar u^n$ (where I changed the notations a bit and took $ x_0 = a,x_1 = b$), and we must show that we can pick $ \alpha,\beta\pmod p$ s.t. $ \alpha u^n + \beta \bar u^n\ne 0,\ \forall n$ in $ \mathbb Z_p$. We can do this by taking $ au\equiv b\pmod p$, which translates (after doing the computations) to $ \beta\equiv 0\pmod p$. Can you explain in detail？

Here's another solution:

abdurashidjon wrote: Is Leva 1980's solution is true? I could not translate to any of $a$ or $b$. Abdurashid $a=1$ and $b=y$.

Bye... Sayantan...

Claim. There is a natural number $b$ such that $b^2=b+1 \pmod{m}$. Proof of Claim. As $m$ is an odd number, it suffices to find a $b$ that $(2b-1)^2 \equiv 5 \pmod{m}$ Set $m=\prod_{i=1}^k p^{e_i}_i$. For each $p_i$, as $(2k)^2 \equiv 5 \pmod{p_i}$, we have $\left( \frac{5}{p} \right)=1$. Now there exists an $x$ such that $x^2 \equiv 5 \pmod{p_i}$ for each $i$. By Hensel's lemma on $f(x)=x^2-5$, we can see that there exists an $x$ that $x^2 \equiv 5 \pmod{p^{e_i}_i}$. By CRT, we can ensure that there exists an $x$ that $x^2 \equiv 5 \pmod{m}$, and we conclude. Now set $x_0=1$ and $x_1=b$. Then $x_n \equiv b^n \pmod{m}$, so $(x_n,m)=1$ as desired.

umm... isn't this just $a=2,b=2k+1$? Take any prime $p$ that divides $4k^2-5$ then $(2k)^2 \equiv 5 (mod p)$ using characteristic polynomials, we get $x_n \equiv 2*(\frac{1+2k}{2})^n (mod p)$ since $p$ is odd and obviously $2k$ is not $-1(modp)$ so $x_n$ coprime to $p$ so it is also coprime to $4k^2-5$ for all n.

Solution: We can take $a=1, b=2k^2+k-2$. Lemma: If we consider the sequence $x_1=1, x_2=s, x_n=x_{n-1}+x_{n-2}$ then all terms of $x_n$ are co-prime to $s^2-s-1$. Proof: Any term of $x_n$ is in the form $sF_r+F_{r-1}$. Now, note that $F_r^2(s^2-s-1)-(sF_r+F_{r-1})(sF_r-F_{r+1})=F_{r-1}F_{r+1}-F_r^2$ which is always of the form $\pm 1$ by Cassini's identity, thus any $x_n$ is coprime to $s^2-s-1$. If we put $s=2k^2+k-2$ note that $(2k^2+k-2)(2k^2+k-3)-1=4k^4+4k^3-9k^2-5k^2+5=(4k^2-5)(k^2+k-1)$ thus for $a=1, b=2k^2+k-2$ the terms are always coprime to $4k^2-5$. @3below(math_pi_rate): The lemma is not true for $p=3$

Nice problem! Here's a different solution (Hopefully correct!): Let $F_n$ denote the Fibonacci sequence with $F_{-1}=1$ and $F_0=0$. It's easy to see (using induction) that $$x_n=aF_{n-1}+bF_n \quad \forall n \in \mathbb{N} \cup \{0\}$$The crucial lemma is as follows:- LEMMA For all primes $p$ such that $5$ is a quadratic residue modulo $p$, there exists some $C \in \mathbb{Z}/ p\mathbb{Z}$ such that $$F_n \not \equiv CF_{n-1} \pmod{p}$$for any $n \in \mathbb{N} \cup \{0\}$. Proof of Claim If $p=5$, then one can easily check that $C=3$ works (since in this case, one finds that $F_n$ is periodic modulo $5$ with period $4$, which is not true). So assume $p>5$, and suppose the Lemma is not true. Then, for all $i \in \mathbb{Z}/ p\mathbb{Z}$, there is some index $n_i \geq 0$ such that $$F_{n_i} \equiv iF_{n_i-1} \pmod{p}$$For all such $i$, let $n_i$ be the smallest such index. Since $\left(\frac{5}{p} \right)=1$, so there exists some $y$ such that $y^2 \equiv 5 \pmod{p}$. Then, by Binet's Formula, \begin{align*} F_n &=\frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2} \right)^n-\left(\frac{1-\sqrt{5}}{2} \right)^n \right) \\ &\equiv \frac{1}{y} \left(\left(\frac{1+y}{2} \right)^n-\left(\frac{1-y}{2} \right)^n \right) \pmod{p} \\ &\equiv \frac{1}{y} \left(\left(\frac{1+y}{2} \right)^{n+p-1}-\left(\frac{1-y}{2} \right)^{n+p-1} \right) \pmod{p} \\ &\equiv F_{n+p-1} \pmod{p} \\ \end{align*}which means that $F_n$ is periodic modulo $p$, with its period $T$ dividing $p-1$. In particular, this gives that $F_{n+T}=F_n$ for some $1 \leq T \leq p-1$. Since $n_0,n_1, \dots ,n_{p-1}$ are the smallest indices by definition, so due to periodicity after $p-1$ indices, we get $0 \leq n_i \leq p-2$. But then, by Pigeonhole Principle, two of these indices must coincide. Suppose $n_i=n_j$ with $i<j$. Then we get $$jF_{n_i-1}=jF_{n_j-1} \equiv F_{n_j} \equiv F_{n_i} \equiv iF_{n_i-1} \pmod{p} \Rightarrow (j-i)F_{n_i-1} \equiv 0 \pmod{p}$$As $0<j-i<p$, so we have $$p \mid F_{n_i-1} \Rightarrow F_{n_i} \equiv iF_{n_i-1} \equiv 0 \pmod{p} \Rightarrow p \mid \gcd(F_{n_i},F_{n_i-1})$$However, this contradicts the well known fact that $\gcd(F_r,F_{r-1})=1$ for all $r \in \mathbb{N} \cup \{0\}$. Thus, we have a contradiction, proving the Lemma. $\Box$ Return to the problem at hand. Let $p_1,p_2, \dots, p_s$ be all distinct prime divisors of $m$. Then $5 \equiv (2k)^2 \pmod{p_i}$ gives that $5$ is a quadratic residue modulo $p_i$ for all $i \in [s]$. By our Lemma, there exist constants $C_1,C_2, \dots ,C_s$ such that $$F_n \not \equiv C_iF_{n-1} \pmod{p_i} \quad \forall n \in \mathbb{N} \cup \{0\} \text{ and } i \in [s]$$Using CRT, there exists an integer $Z$ satisfying $$Z \equiv C_i \pmod{p_i} \quad \forall i \in [s]$$Choose $b=1$ and $a>0$ with $a \equiv -Z \pmod{m}$. Then, for all $i \in [s]$, we get $$x_n=aF_{n-1}+bF_n \equiv F_n-ZF_{n-1} \not \equiv 0 \pmod{p_i} \Rightarrow \gcd(x_n,m)=1 \quad \forall n \geq 0 \text{ } \blacksquare$$

@above your lemma is valid for any $p $, notice you're not using the fact $\left (\frac {5}{p}\right)=1$.

Al3jandro0000 wrote: @above your lemma is valid for any $p $, notice you're not using the fact $\left (\frac {5}{p}\right)=1$. I am using it in the proof of the Lemma while writing $\sqrt{5}$ as $y$. Note that if $5$ was not a quadratic residue, then I would have to work in $\mathbb{Z}[\sqrt{5}]$, and so Fermat's Little Theorem won't be applicable (Lagrange's Theorem gives a higher bound on the order, which isn't compatible with my PHP usage). On the orther hand, there might be a possibility of the Lemma being true for all primes. I wonder if someone can prove/disprove that?

..................

Tbh I don't think the Lemma is true always (In fact, one can easily check that it fails for $p=3$). However, it can be interesting to determine for what values of $p$ it works. Here are some comments PMed to me by Superguy (I haven't read it thoroughly, but it seems ok at first glance). Superguy in First PM wrote: Okay so far I have approached problem a bit. First of all I have neglected the $F_{-1}$ part which won't change much of the proof Assume ftsoc that there doesn't exist such a $C$ By considering the group $\mathbb{Z}[\frac{1+\sqrt{5}}{2}]$ we can see that if $\left (\frac {5}{p}\right)=-1$ then $p$ is a prime in $\mathbb{Z}[\frac{1+\sqrt{5}}{2}]$ Now using some tricks u can get that $a^{(p+1)}\equiv -1 \pmod{p}$ where $a$ is golden ratio. Using this u can easily get $F_{n+p+1}\equiv -F_{n}\pmod{p}$ We get that period is atmost $2p+2$ So considering the sets $(F_{1},F_{2},.....F_{p+1})$ and $(F_{p+2},F_{p+3}......F_{2p+2})$ and using the minimal index notation one can see that $2\leq n_{i}\leq p+1$ This means that there should be $p$ i's given by $p$ $n_{i}$'s which implies each member of first set should give a separate $i$ For instance in case of $p=3$ clearly no such constant exists while in the case $p=17$ we clearly have a constant as $F_{9}\equiv F_{18}\equiv 0\pmod{17}$ Edit:See below for a bit more detailed explanation. Superguy in Second PM wrote: Hmm a bit more So clearly there should not be any index $0<i<p+1$ such that $p|F_{i}$ otherwise we can get our constant from above argument. Now assuming for no such index $F_{i}$ is multiple of $p$. Hence all $(\frac{F_{i}}{F_{i-1}})$ are uniquely defined modulo $p$ Now assuming that two of them are congruent then $\frac{F_{i}}{F_{i-1}}\equiv \frac{F_{m}}{F_{m-1}}\pmod{p}$ for some $m>i$ Now manipulating terms we get $(\frac{1+\sqrt{5}}{1-\sqrt{5}})^{m-j}\equiv 1\pmod{p}$. Now clearly we can show that order divides $2(p+1)$ and hence if order is less than $(p+1)$ then we can clearly get $(m,j)$ and thus our desired constant however in case order is equal to $2(p+1)$ or $(p+1)$ we can't get our desired constant. Others can comment on this if they find something interesting

Well last part can be reduced to the fact that such a constant exists only if $F_{p+1}$ doesn't has a primitive prime divisor as $p$ which I don't think is possible to prove. For instance after $p=3$ next such prime for which no such constant exists is $p=7$ followed by $p=23$

Lemma. If $p$ is a prime such that $p|4k^2-5$ then we can pick $a,b$ such that for all $N\in\mathbb N$ we have $p\nmid x_n$. Proof. CASE I: $p=5$. It suffices to take $a=1$ and $b=3$ CASE II: $p\neq 5$ Now let $F_0=0, F_1=1$ and $F_n$ be the $n^{th}$ Fibonacci number. It is easy to show that $$x_{n+2}=F_{n+1}a+F_nb$$CLAIM 1. $F_p\equiv 1\pmod p$ Proof. Using the general term formular for Fibonacci sequence, \begin{align*} F_p&=\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^p-\left(\frac{1-\sqrt{5}}{2}\right)^p\right)\\ &=\frac{2}{2^p\sqrt 5}(\sum_{i=0}^{\frac{p-1}{2}}\sqrt 5\binom{p}{2i+1}5^i)\\ &\equiv\frac{1}{2^{p-1}}5^{\frac{p-1}{2}}\\ &\equiv5^{\frac{p-1}{2}} \pmod{p} \end{align*}The first equivalence follows from $p|\binom{p}{2i+1}$ for all $1\leq i\leq \frac{p-3}{2}$The last equvialence follow from $p\neq 2$ and Fermat little theorem. Now notice that $p|4k^2-5$, hence by Euler's criterion we have $$5^{\frac{p-1}{2}}\equiv \left(\frac{5}{p}\right)=1\pmod p$$This proves CLAIM 1. $\blacksquare$ CLAIM 2. $F_{p-1}\equiv 0\pmod p$ Proof. The proof is similar to CLAIM 1. Again, using the general term formula for Fibonacci sequence, \begin{align*} F_{p-1}&=\frac{1}{\sqrt 5}\left(\left(\frac{1+\sqrt 5}{2}\right)^{p-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{p-1}\right)\\ &=\frac{1}{2^{p-2}}\sum_{i=1}^{\frac{p-3}{2}}\binom{p-1}{2i+1}5^i \end{align*}Notice that $$\binom{p-1}{2i+1}=\frac{(p-1)!}{(2i+1)!(p-2i+1)!}\equiv \frac{(p-1)!}{(-1)^{2i+1}(p-1)!}\equiv -1\pmod p$$Hence $$F_{p-1}\equiv -\frac{1}{2^{p-2}}\sum_{i=1}^{\frac{p-3}{2}}5^i=-\frac{5^{\frac{p-1}{2}}-1}{4\cdot 2^{p-2}}\equiv 0\pmod p$$$\blacksquare$ Now this implies that $x_{n+p-1}\equiv x_n \pmod p$ for all $n\in\mathbb N$. We now take $a=1$. It suffices to find $b$ which satisfies $$F_{i+1}+F_ib\not\equiv 0\pmod p$$for all $0\leq i\leq p-2$. Notice that there exists at most $1$ $b$ which satisfies $$F_{i+1}+F_ib\equiv 0\pmod p$$Since there are only $p-1$ incongruences, each of which eliminates at most $1$ chocie of $b$, together with the fact that there are $p$ residue classes modulo $p$, which gives $p$ choices for $b$, we conclude that we can always pick such $p$. This proves the lemma. $\blacksquare$ Now let $p_1,...,p_n$ be the prime factors of $m$. Then from the lemma for each $i$ we can pick $a_i$ and $b_i$ so that the sequence defined by $x_0=a_i$, $x_1=b_i$ and $$x_{n+2}=x_{n+1}+x_n$$has all its terms relatively prime to $p_i$. Now by Chinese Remanider Theorem there exists integers $a$ and $b$ satisfying $$a\equiv a_i\pmod{p_i}$$$$b\equiv b_i\pmod{p_i}$$Now by taking this $a$ and $b$ the proof is completed.

By CRT, it suffices to show the problem for $p\mid 4k^2-5$ where $p$ is a prime. Note that \[x_n = F_{n-1}a + F_n b,\]and since $(\tfrac{5}{p})=1$, we have that $F_{n+p-1}\equiv F_n\pmod{p}$ by Binet's thereom and Fermat's little theorem. Let $t$ be the smallest positive integer such that $p\mid F_t$, so $t$ is the order of $\tfrac{1+\sqrt{5}}{1-\sqrt{5}}$ mod $p$, so $t\mid p-1$. Now, if $t\nmid n$, then $\tfrac{F_{n-1}}{F_n}$ can take at most $t-1$ values (since it repeats mod $t$), so it takes at most $p-2$ values, so there is some nonzero value mod $p$ it never achieves. Let this value be $c$. Take $a=1$, $b\equiv -c\pmod{p}$. Then, \[x_n = F_{n-1}a + F_n b\equiv F_{n-1}-F_nc\pmod{p}.\]If $t\mid n$, then $F_n\equiv 0\pmod{p}$ and $F_{n-1}\not\equiv 0\pmod{p}$ (else $p\mid F_m$ for all $m$ which is not true), so $p\nmid x_n$. If $t\nmid n$, then $F_n\not\equiv 0\pmod{p}$, so this is never $0$ by the selection of $c$. Thus, these values of $a$ and $b$ yield all $x_n$ relatively prime to $p$, as desired.

Note that \[x_n = F_{n-1}a + F_n b,\]Claim: There is a natural number $b$ such that $b^2=b+1 \pmod{m}$ Proof: We need $(2b-1)^2 \equiv 5 \pmod m$ i.e $5$ is a quadratic residue modulo $m$ Suppose that $m=\prod_{i=1}^{x} {p_i}^{e_i}$ By Hensel's Lemma,we can assure that each congruence has a solution and we can conclude by CRT.(here $f'(x)=8b-4$,and clearly we can choose such an $b$ s.t $ p \nmid 8b-4$ to get a solution.) Now choose $a=1$ and clearly $x^n \equiv b^n \neq 0 \pmod m$ and $\gcd(x_n,m)=1$(by induction.

Is this right? This seems like a troll solution. It's sufficient to construct a sequence mod all primes $p$ dividing $4k^2-5$, then combine them using CRT. If $p \mid 4k^2-5$, then $p$ is odd and $5$ is a quadratic residue $\!\!\!\mod p$. Let $a=1$, and choose $b$ such that $(2b-1)^2 \equiv 5 \pmod{p}$. It's easy to check that this condition forces $\frac{x_4}{x_3}=\frac{3b+2}{2b+1}=b=\frac{x_1}{x_0} \pmod{p}$ if $x_3$ is nonzero $\!\!\!\mod{p}$. Now, we check that $x_1,x_2,x_3 \not\equiv 0 \pmod{p}$: If $x_1=b \equiv 0 \pmod{p}$, then $(2b-1)^2 \equiv 1 \equiv 5 \pmod{p}$, so $p=2$, a contradiction. If $x_2=b+1 \equiv 0 \pmod{p}$, then $(2b-1)^2 \equiv 9 \equiv 5 \pmod{p}$, so $p=2$, a contradiction. If $x_3=2b+1 \equiv 0 \pmod{p}$, then $(2b-1)^2 \equiv 4 \equiv 5 \pmod{p}$, so there are no choices of $p$, a contradiction. Since $\frac{x_3}{x_0} \equiv \frac{x_4}{x_1} \pmod{p}$, we know that $\frac{x_{n+3}}{x_n} \equiv \frac{x_3}{x_0} \pmod{p}$. Therefore, we can write $x_n=x_i \cdot \left(\frac{x_3}{x_0}\right)^{\left\lfloor \frac{n}{3} \right\rfloor}$, where $i \in \{0,1,2\}$. This is nonzero $\!\!\!\mod{p}$, so we are done.

Let $p$ be a prime and $p|m$. Note $p$ is odd. Let $a\equiv 1\pmod{p}$ and $b\equiv k+2^{-1}\pmod{p}$. Assume towards a contradiction $b\equiv 0\pmod{p}$. Then, $2k\equiv -1\pmod{p}$. Then, $5\equiv 4k^2\equiv 1\pmod{p}$, so $p|4$, so $p=2$, a contradiction. We have $$b^2\equiv k^2+k+2^{-2}\equiv 2^{-2}(4k^2+4k+1)\equiv 2^{-2}(5+4k+1)\equiv 2^{-1}(2k+3)\equiv k+2^{-1}+1\equiv b+1\pmod{p}.$$ We claim $x_n\equiv b^n\pmod{p}$. We will prove it with induction with $n=0, 1$ as the base case. We have $$x_n\equiv x_{n-1}+x_{n-2}\equiv b^{n-1}+b^{n-2}\equiv b^{n-2}(b+1)\equiv b^n\pmod{p}.$$So, since $b\not \equiv 0\pmod{p}$, none of the $x_n$ are equivalent to $0\pmod{p}$. Thus the whole sequence is relatively prime for $p$. So, for each prime $p|m$, there exists a residue $b_p$ such that when $x_0\equiv 1\pmod{p}$ and $x_1\equiv b_p\pmod{p}$, $x_i$ is never a multiple of $p$. By the Chinese Remainder Theorem, there exists $B$ such that $B\equiv b_p\pmod{p}$ for all $p|m$. When $a=1$ and $b=B$, the sequence will always be relatively prime to $m$.

Let $a=1$ and $b=2k^2+k-2$. $$(2k+k-2)^2-(2k+k-2)-1=(4k^2-5)(k^2-k-1) \implies (2k+k-2)^2 \equiv (2k+k-2)+1 \pmod{m} \implies 2k^2+k-2 \perp m \text{ and } x_n \equiv (2k^2+k-2)^n \pmod{m}.~\blacksquare$$

Ok so the motivation of the above solution comes from the fact that for each prime $p$ dividing $m$ we can write $\sqrt{5} \equiv 2k$ and the recursion can be characterized as usual in the form $$x_n \equiv x\left(\frac{1+2k}{2}\right)^n+y\left(\frac{1-2k}{2}\right)^n$$and it clearly necessary that all of these should be nonzero mod $p$ (in fact by CRT it is also sufficient, so we've reduced the problem to this). The best way to deal with this is to do the stupidest thing possible and set $y=0$ which yields (after adding $4k^2-5$) the above solution.

Note that $5$ is always a quadratic residue of any $p\mid m$. Let $(2k-1)^2\equiv 5\pmod p$ then $p\mid k^2-k-1$. Then pick $a=1$, $b\equiv k\pmod p$, and we see that $x_n\equiv k^n\pmod p$ and by CRT we're done.

We show that for each prime divisor $p$ of $m$, we can find some $a_p$ and $b_p$ so that $\left(x_n\right)$ has all its terms nonzero modulo $p$. Let $p$ be a prime divisor of $m$. If $5$ is a prime divisor of $m$ and $p=5$, we take $a_5=1$ and $b_5=3$. Then $\left(x_n\right)$ repeats $1, 3, 4, 2, 1, 3,\dots$ modulo $5$, with all terms being nonzero.

We have \[\alpha^2\equiv \frac{1+4k+4k^2}{4}\equiv \frac{6+4k}{4}\equiv \frac{3+2k}{2}\equiv \alpha + 1\]This also implies $\alpha\not\equiv 0$. Now, let $a_p\equiv 1$ and $b_p\equiv \alpha$. We claim by induction that $x_n\equiv \alpha^n$. We have the base cases $n=0$ and $n=1$ already. Then for the induction step, we have for $n\geq 2$ that \[x_n\equiv x_{n-1}+x_{n-2}\equiv \alpha^{n-1}+\alpha^{n-2}\equiv \alpha^{n-2}(\alpha+1)\equiv \alpha^{n-2}\alpha^2\equiv \alpha^n\]which completes the induction. Then, since $\alpha\not\equiv 0$, all terms of $\left(x_n\right)$ are nonzero modulo $p$. Using the Chinese Remainder Theorem, we can guarantee the existence of $a$ and $b$ such that $a\equiv a_p\pmod{p}$ and $b\equiv b_p\pmod{p}$ for all prime divisors $p$ of $m$. This guarantees that $\left(x_n\right)$ will have all its terms not divisible by any prime divisor of $m$, and thus relatively prime to $m$.

An alternative continuation after the $x_n = x(\frac{1+k}{2})^n + y(\frac{1-k}{2})^n$ construction: There are at most $p-1$ possible unique modulo $p$ pairs for $((\frac{1+k}{2})^n,(\frac{1-k}{2})^n)$ Each pair eliminates at most $p$ different potential pairs $(x,y)$ We are done as there must be at least one pair leftover