I will write complete solution on request, but I think this will be enough. I was working with sequence $ y_i = \frac {x_i}2$, so I will solve the problem for this sequence, it's the same for $ x_i$. First of all $ y_n = \frac {(3 + \sqrt {8})^n - (3 - \sqrt {8})^n}{2\sqrt {8}} = \binom {n}1 3^{n - 1} + \binom{n}3 3^{n - 3}8 + \binom{n}5 3^{n - 5}8^2 + ...$, so for prime $ p > 3$ it follows $ y_p\equiv _p \pm 1$, and $ y_{p + 1} \equiv_p 3^p + 3y_p\equiv_p 0,6$, but if $ y_{p + 1}\equiv_p 6$ then because $ y_p \equiv_p 1$ it's $ y_{p - 1} \equiv_p 0$, so $ p|y_{p - 1}y_{p + 1}$. Then, we can prove the following: let $ q$ be a prime $ q\not | 6$ and $ k$ is the smallest natural number such that $ q|y_k$, then $ q|y_n$ if and only if $ k|n$.Just observe $ y_k$, by induction $ y_{k + i} \equiv_q - y_{k - i}$ for $ i\leq k$, and that's it. Because $ q$ is a prime divisor of $ y_p$ where $ p$ is prime, then $ q$ doesn't divide any $ y_i$ where $ i < p$ and $ p<i<2p$. Suppose that $ q < 2p - 1$, because $ q|y_{q - 1}y_{q + 1}$ but $ q - 1$ and $ q + 1$ are different from $ p$ and $ 2p$. Bye

I think you can also solve it using some basic group theory: We can compute: $ x_{p} = \frac { (3 + \sqrt{8} )^p - (3 - \sqrt{8})^n } { \sqrt{8} }$. Case 1: $ \sqrt {8}$ exists in $ \mathbb{Z}_{q}$. Then let $ a = \sqrt{8}$. If $ q \neq 2$, $ \sqrt{8}$ will not vanish in $ Z_{q}$ so we won't be dividing by $ 0$. Also, clearly $ \sqrt{8} \neq 3,-3 (mod\ q)$. Then we have: $ (3+a)^p \equiv (3-a)^p (mod\ q)$. $ (\frac {(3+a)^2}{(3+a)(3-a)})^{p} \equiv 1 (mod\ q)$ $ (3+a) ^ {2p} \equiv 1 (mod\ q)$ so the order of $ 3+a$ divides $ 2p$ and it divides $ q-1$, so it divides $ gcd(2p,q-1)$. If this order is $ 2$, then we can quickly conclude that $ q=2$ (since $ (3+ \sqrt{8})^2 \equiv 1 (mod\ q)$ ). Thus, otherwise this order must be at least $ 4$ - for this to occur we clearly require that $ p|q-1$, and since $ q \geq 5$, we conclude $ q-1 \geq 2p$, finishing off this case. Case 1: $ \sqrt {8}$ does not exist. In this case we consider the group $ \mathbb{Z}_{q}[ \sqrt {8} ]$. Like in Case 1 we obtain: $ (3 + \sqrt{8})^{2p} \equiv 1 (mod\ q)$ Since order of the element $ 3 + \sqrt{8}$ divides the order of the group, $ q^2 - 1$, we have: order of $ 3+\sqrt{8}$ divides $ 2p$ and $ (q-1)(q+1)$, and thus $ gcd (2p, (q-1)(q+1))$. Similarly to Case 1, we can verify that for $ q \neq 2,3$, the order of $ 3 + \sqrt{8}$ is larger than $ 2$ - for this to occur, $ p | q-1$ or $ p | q+1$. Since $ p =q-1, q+1$ is unacceptable, it follows that $ q \geq 2p-1$ either way.

SpongeBob wrote: First of all $ y_n = \frac {(3 + \sqrt {8})^n - (3 - \sqrt {8})^n}{2\sqrt {8}} = \binom {n}1 3^{n - 1} + \binom{n}3 3^{n - 3}8 + \binom{n}5 3^{n - 5}8^2 + ...$, so for prime $ p > 3$ it follows $ y_p\equiv _p \pm 1$, and $ y_{p + 1} \equiv_p 3^p + 3y_p\equiv_p 0,6$, but if $ y_{p + 1}\equiv_p 6$ then because $ y_p \equiv_p 1$ it's $ y_{p - 1} \equiv_p 0$, so $ p|y_{p - 1}y_{p + 1}$. This line looks messy, could you elaborate on it?

I paste three solutions below

Attachments:

Dear hxy09, You can post English Solution in here, please. Thank you

duythuc_lqd wrote: Dear hxy09, You can post English Solution in here, please. Thank you Firstly,I am sorry for creating obstacles for reading solutions,here is the sketch of solution 3,which is regarded as the best solution of this problem Let $ y_n = \frac {x_n}{2}$ then $ y_n$ is an integer sequence such that $ y_1 = 1,y_2 = 6$,$ y_{n + 2} = 6y_{n + 1} - y_n$ A famous result(prove it by induction) state that $ y_{m + n} = y_{m + 1}y_n - y_my_{n - 1}$thus $ (y_m,y_n) = y_{(m,n)}$ (Euclidean algotithm) $ y_{n} = \frac {(3 + \sqrt {8})^{n} - (3 - \sqrt {8})^{n}}{2\sqrt {8}} = \frac {\alpha ^n - \beta^n}{\alpha - \beta}$ then $ q|y_{\frac {q - 1}{2}}y_{\frac {q + 1}{2}}$ (don't hesitate to expand it!) $ q|y_p$ we conclude $ p|\frac {q - 1}{2}$ or $ p|\frac {q + 1}{2}$ hence $ q\ge 2p - 1$ QED

I haven't done much work with finite fields, but can someone please check for mistakes in the following solution? So as above, we can easily derive that $a_n = \frac{(\sqrt{2}+1)^{2n}-(\sqrt{2}-1)^{2n}}{2\sqrt{2}}$. Now we consider the sequence in the finite field $\mathbb{F}_{q^2}$. Note that all zero elements of $\mathbb{F}_q$ are zero elements in $\mathbb{F}_{q^2}$. So if $q \not= 2$, \[a_p = 0\implies (\sqrt{2}+1)^{2p}-(\sqrt{2}-1)^{2p} = 0 \implies (\sqrt{2}+1)^{4p}-1 = 0\] (I multiplied both sides by $(\sqrt{2}+1)^{2p}$, and its easy to see $\sqrt{2}+1 \not= 0$ for any $q \not= 2$.) Note that $(\sqrt{2}+1)^4-1 = 4\sqrt{2} \cdot (\sqrt{2}+1)^2 \not= 0$. So $p$ divides the order of $\sqrt{2}+1$ in $\mathbb{F}_{q^2}$. Therefore by Lagrange's Theorem on $\mathbb{F}_{q^2}^*$, $p \vert q^2-1$, and since $p, q$ are odd primes, $q \ge 2p-1$.

<hxy09> wrote: then $ q|y_{\frac {q - 1}{2}}y_{\frac {q + 1}{2}}$ $ q|y_p$ we conclude $ p|\frac {q - 1}{2}$or $ p|\frac {q + 1}{2}$ can you elaborate this please? I can't understand why...

@above, because for prime $q>2,\ q\mid x\implies q\mid\tfrac{x}{2^{v_2(x)}}$, and we have that $2\mid q\pm1$, but $q>2$, so $v_2(q\pm 1)>0$. As an aside, isn't this problem a bit too straightforward for a TST Edit: I was referring to the Finite Fields approach

We actually claim the following: \[p\mid x_k,\qquad k=\frac{p-\left(\frac 2p\right)}2\]To show this implies the statement, note that if the smallest index $n$ such that $x_n\equiv 0\pmod p$, then as $p\mid x_0$, we can get that if $x_k\equiv 0\pmod p$, then $n\mid k$ (otherwise, we can note that if $k=qn+r$ for $0<r<n$, then $x_r\equiv 0\pmod p$, absurd). First, we find the recurrence for the sequence to be \[x_n=\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^n-(3-2\sqrt 2)^n\right)\]We shall prove this by induction: Base Case. $n=0,1$ (we can take $n=0$ by extending backwards). In this case, \[x_0=0=\frac 1{2\sqrt 2}(1-1)=\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^0-(3-2\sqrt 2)^0\right)\]\[x_1=2=\frac 1{2\sqrt 2}((3+2\sqrt 2)-(3-2\sqrt 2))=\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^1-(3-2\sqrt 2)^1\right)\]Induction Hypothesis. Assume the result holds for $n=k,k-1$ for $k\geq 1$. We show it holds for $n=k+1$. Induction Step. Note that \begin{align*} &\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^{k+1}-(3-2\sqrt 2)^{k+1}\right)=\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^{k-1}(17+12\sqrt 2)-(3-2\sqrt 2)^{k-1}(17+12\sqrt 2)\right) \\&=6\cdot\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^k-(3-2\sqrt 2)^k\right)-\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^{k-1}-(3-2\sqrt 2)^{k-1}\right) \\&=6x_k-x_{k-1} \\&=x_{k+1}\end{align*}completing the proof. $\blacksquare$ Now, if $\left(\frac 2p\right)=1$, then $3\pm2\sqrt2=(1\pm\sqrt2)^2\in\mathbb F_p$, so thus by Fermat's Little Theorem, we get \begin{align*} x_{(p-1)/2}&=\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^{(p-1)/2}-(3-2\sqrt 2)^{(p-1)/2}\right) \\&=\frac 1{2\sqrt 2}\left((1+\sqrt2)^{p-1}-(1-\sqrt2)^{p-1}\right) \\&\equiv 0\pmod p \end{align*}In the other case, we can note \[(1\pm\sqrt2)^p\equiv 1^p\pm\sqrt2^p\equiv 1\mp\sqrt2\pmod p\]when working in $\mathbb Z_p[\sqrt 2]$ (as binomial coefficients are 0). Thus, \begin{align*} x_{(p+1)/2}&=\frac 1{2\sqrt 2}\left((3+2\sqrt 2)^{(p+1)/2}-(3-2\sqrt 2)^{(p+1)/2}\right) \\&=\frac 1{2\sqrt 2}\left((1+\sqrt2)^{p+1}-(1-\sqrt2)^{p+1}\right) \\&\equiv \frac 1{2\sqrt 2}\left((1+\sqrt2)(1-\sqrt 2)-(1-\sqrt 2)(1+\sqrt 2)\right) \\&\equiv 0\pmod p \end{align*} Bye.