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), \quad 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 \neq 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} \pmod{q}$ as $a \equiv c \pmod{q}$ and $b \equiv d \pmod{q}$.

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

On the other hand, if $q \mid b_n$, write $n = du + r$, $0 \le r < d$. Suppose $r \ge 1$, from
$$\begin{aligned} 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}) \pmod{q}, \end{aligned}$$
we have
$$a_d^u b_r \equiv 0 \pmod{q}. \qquad \textcircled{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 \binom{q}{i}$, $i = 1, 2, \dots, q-1$.

Using Fermat's little theorem, we have
$$3^q \equiv 3 \pmod{q}, \quad 2^q \equiv 2 \pmod{q}.$$
As $q \neq 2$, so $2^{\frac{q-1}{2}} \equiv \pm 1 \pmod{q}$, we get
$$\begin{aligned} (3+2\sqrt{2})^q &= \sum_{i=0}^{q} \binom{q}{i} \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} \pmod{q}. \end{aligned}$$
By the same argument, we have
$$(3+2\sqrt{2})^{q^2} \equiv (3 \pm 2\sqrt{2})^q \equiv 3+2\sqrt{2} \pmod{q}.$$
So
$$(a_{q^2-1} + \sqrt{2}b_{q^2-1})(3 + 2\sqrt{2}) \equiv 3 + 2\sqrt{2} \pmod{q}.$$
Thus,
$$\begin{cases} 3a_{q^2-1} + 4b_{q^2-1} \equiv 3 \pmod{q}, \\ 2a_{q^2-1} + 3b_{q^2-1} \equiv 2 \pmod{q}. \end{cases}$$
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$.