China National Team Selection Test

It is easy to see $$x_n=\frac{1}{2\sqrt{2}}\left((3+2\sqrt{2}{)}^n-(3-2\sqrt{2}{)}^n\right),n=1,2,\dots$$ Let $a_n,b_n$ be positive integers and $a_n+b_n\sqrt{2}=(3+2\sqrt{2}{)}^n$. Then $$a_n-b_n\sqrt{2}=(3-2\sqrt{2}{)}^n,$$ so $x_n=b_n$, and $a_n^2-2b_n^2=1$, $n=1,2,\dots$

Suppose $q\ne 2$. Since $q\mid x_p$, thus $q\mid b_p$, so there exists a term in $\{b_n\}$ which is divisible by $q$. Let $d$ be the least number such that $q\mid b_d$. We have the following lemma.

Lemma For any positive integer $n$, $q\mid b_n$ if and only if $d\mid n$.

Proof: For $a,b,c,d\in \mathbb{Z}$, denote $a+b\sqrt{2}\equiv c+d\sqrt{2}(\mathrm{mod}q)$ as $a\equiv c(\mathrm{mod}q)$ and $b\equiv d(\mathrm{mod}q)$.

If $d\mid n$, write $n=du$, then $$a_n+b_n\sqrt{2}=(3+2\sqrt{2}{)}^{du}\equiv a_d^u(\mathrm{mod}q),$$ so $b_n\equiv 0(\mathrm{mod}q)$.

On the other hand, if $q\mid b_n$, write $n=du+r$, $0\le r<d$. Suppose $r\ge 1$, from $$\begin{array}{rl}{a}_n& =(3+2\sqrt{2}{)}^n=(3+2\sqrt{2}{)}^{du}\cdot (3+2\sqrt{2}{)}^r\\ & \equiv a_d^u(a_r+b_r\sqrt{2})(\mathrm{mod}q),\end{array}$$ we have $$a_d^u{b}_r\equiv 0(\mathrm{mod}q).\stackrel{◯}{1}$$ But $a_d^2-2b_d^2=1$, and $q\mid b_d$; so $q\nmid a_d^2$. Since $q$ is a prime, therefore $q\nmid a_d$, and $(q,a_d^u)=1$. From (1) we have $q\mid b_r$, it contradicts the definition of $d$. So $r=0$, and the lemma is proven.

Now, as $q$ is a prime, so $q\mid \left(\genfrac{}{}{0ex}{}{q}{i}\right)$, $i=1,2,\dots ,q-1$.

Using Fermat's little theorem, we have $$3^q\equiv 3(\mathrm{mod}q),2^q\equiv 2(\mathrm{mod}q).$$ As $q\ne 2$, so $2^{\frac{q-1}{2}}\equiv \pm 1(\mathrm{mod}q)$, we get $$\begin{array}{rl}(3+2\sqrt{2}{)}^q& =\sum _{i=0}^q\left(\genfrac{}{}{0ex}{}{q}{i}\right)\cdot 3^{q-i}(2\sqrt{2}{)}^i\\ & \equiv 3^q+(2\sqrt{2}{)}^q\\ & =3^q+2^q\cdot 2^{\frac{q-1}{2}}\sqrt{2}\\ & \equiv 3\pm 2\sqrt{2}(\mathrm{mod}q).\end{array}$$ By the same argument, we have $$(3+2\sqrt{2}{)}^{q^2}\equiv (3\pm 2\sqrt{2}{)}^q\equiv 3+2\sqrt{2}(\mathrm{mod}q).$$ So $$(a_{q^2-1}+\sqrt{2}{b}_{q^2-1})(3+2\sqrt{2})\equiv 3+2\sqrt{2}(\mathrm{mod}q).$$ Thus, $$\{\begin{array}{l}3a_{q^2-1}+4b_{q^2-1}\equiv 3(\mathrm{mod}q),\\ 2a_{q^2-1}+3b_{q^2-1}\equiv 2(\mathrm{mod}q).\end{array}$$ We know that $q\mid b_{q^2-1}$.

Since $q\mid b_p$, from the lemma, we have $d\mid p$. So $d\in \{1,p\}$, and if $d=1$, then $q\mid b_1=2$, contradiction! So $d=p$, hence $q\mid b_{q^2-1}$. So $p\mid q^2-1$, thus $p\mid q-1$ or $p\mid q+1$. Since $q-1$ and $q+1$ are even, so $q\ge 2p-1$.