# 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.)

• If $n=9$, there is the sequence $(1,8),(8,55),(55,377),(277,2584)$ – Michael Aug 30 '17 at 9:40

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)$.

• if $a_k =(n-2)a_{k-1}-a_{k-2}$ and $a_{k-2}^2 = n \mod a_{k-1}$ then also $a_k^2 = n \mod a_{k-1}$ you need to prove also that $a_{k-1}^2 = n \mod a_k$. – Ahmad Aug 30 '17 at 10:33
• Thanks for the good construction for general $n$, how about the case that n is a negative integer ? – user395911 Aug 30 '17 at 17:01
• And what's the motivation of defining the sequences in the case $n=3$？ – user395911 Aug 30 '17 at 17:20
• The motivation is to show that there are an infinite number of solutions for the $n=3$ case. You can construct a new solution $x_n,y_n$ from the previous two solutions in the sequence. I haven't proved that the sequence only produces solutions, but with induction it should be possible to show it. – Jaap Scherphuis Aug 30 '17 at 17:37
• @ZhiyuZhang: I have edited my answer to include solutions for non-positive $n$. – Jaap Scherphuis Aug 30 '17 at 18:14