, 2011

Let $3n + 1 = x^2$ and $4n + 1 = y^2$. Then $y^2 - x^2 = n$. As $y$ is odd, $y^2 \equiv_8 1$, so $n$ has to be even, therefore $x$ is odd, and therefore $y^2 - x^2 \equiv_8 1 - 1 = 0$, hence $8|n$.

Now notice that $4x^2 - 3y^2 = 1$, so setting $w = 2x$ we obtain Pell's equation $w^2 - 3y^2 = 1$. This has solutions $(2 + \sqrt{3})^m = w_m + \sqrt{3}y_m$, but only the odd $m$ solutions correspond to an even $w_m$. Starting with the base solution $2 + \sqrt{3}$, and multiplying through by $(2 + \sqrt{3})^2$ we get the recursions
$$w_{m+1} = 2x_{m+1} = 14x_m + 12y_m, \quad \text{and} \quad y_{m+1} = 8x_m + 7y_m.$$
Then $x_{m+1} = 7x_m + 6y_m \equiv_7 -y_m$, and $y_{m+1} = 8x_m + 7y_m \equiv_7 x_m$, hence $y_{m+1}^2 - x_{m+1}^2 \equiv_7 x_m^2 - y_m^2$, and by induction, $x_m^2 - y_m^2 \equiv_7 0$. Hence 7 divides $n = y_m^2 - x_m^2$.