Existence of infinitely many solutions to $x^2 \equiv n \bmod y, \ y^2 \equiv n \bmod x$ Let $n$ be a given integer, consider the following equation for $x,y \in \mathbb Z$:
$$x^2 \equiv n \bmod y,\  y^2 \equiv n \bmod x$$
Are there infinitely many solutions to this equation for every $n$? 
If $n=d^2$ is a square, then it's easy to see $y=x+d$ will give infinitely many solutions. But in general, I don't have any idea to do such construction. (Anyway, $x=y=n$ will be a solution.)
 A: I've done a bit of exploring by computer, and my results are as follows, presented without proofs.
For every $n>3$ we can generate an infinite sequence of solutions.
Define a sequence by $a_{k}=(n-2)a_{k-1}-a_{k-2}$, with $a_1=1$ and $a_2=n-1$.
It is fairly straightforward to prove using induction that $a_k^2 = a_{k-1}a_{k+1} + n$. From this it follows that any pair of consecutive elements of the sequence, $x=a_k$, $y=a_{k+1}$, satisfies the equations. 
So for $n=4$ you get $1, 3, 5, 7, 9, 11, 13,...$.
For $n=5$ you get $1, 4, 11, 20, 76, 199, 521,...$.
For $n=6$ you get $1, 5, 19, 71, 265, 989,...$.
For $n=7$ you get $1, 6, 29, 139, 666,...$.
etc.
The same construction also works for $n<0$.
So for $n=-1$ you get $1, -2, 5, -13, 34, ...$.
For $n=-2$ you get $1, -3, 8, -21, 85, ...$.
etc.
For $n=0$ you have the infinitely many solutions: $x=k$, $y=k$ for any $k$.
For $n=1$ you have the infinitely many solutions: $x=k$, $y=1$ for any $k$.
For $n=3$ there is a different recursive formula for an infinite sequence of solutions.$(x_n,y_n)=$ $(6,3)$, $(69,39)$, $(753,426)$, $(8214,4647)$, $(89601,50691)$, $...$
These satisfy $x_k=11x_{k-1}-x_{k-2}$ and $y_k=11y_{k-1}-y_{k-2}$.
$n=2$ is the hardest case. I only found the following solutions: $(1,1)$, $(2,2)$, $(1262,94)$, and $(3602578,58594)$.
